// Path: Labs/resources/net/datastructures/Edge.java
// public interface Edge<E> {
//   /** Returns the element associated with the edge. */
//   E getElement();
// }
// 
// Path: Labs/resources/net/datastructures/Graph.java
// public interface Graph<V,E> {
// 
//   /** Returns the number of vertices of the graph */
//   int numVertices();
// 
//   /** Returns the number of edges of the graph */
//   int numEdges();
// 
//   /** Returns the vertices of the graph as an iterable collection */
//   Iterable<Vertex<V>> vertices();
// 
//   /** Returns the edges of the graph as an iterable collection */
//   Iterable<Edge<E>> edges();
// 
//   /**
//    * Returns the number of edges leaving vertex v.
//    * Note that for an undirected graph, this is the same result
//    * returned by inDegree
//    * @throws IllegalArgumentException if v is not a valid vertex
//    */
//   int outDegree(Vertex<V> v) throws IllegalArgumentException;
// 
//   /**
//    * Returns the number of edges for which vertex v is the destination.
//    * Note that for an undirected graph, this is the same result
//    * returned by outDegree
//    * @throws IllegalArgumentException if v is not a valid vertex
//    */
//   int inDegree(Vertex<V> v) throws IllegalArgumentException;
// 
//   /**
//    * Returns an iterable collection of edges for which vertex v is the origin.
//    * Note that for an undirected graph, this is the same result
//    * returned by incomingEdges.
//    * @throws IllegalArgumentException if v is not a valid vertex
//    */
//   Iterable<Edge<E>> outgoingEdges(Vertex<V> v) throws IllegalArgumentException;
// 
//   /**
//    * Returns an iterable collection of edges for which vertex v is the destination.
//    * Note that for an undirected graph, this is the same result
//    * returned by outgoingEdges.
//    * @throws IllegalArgumentException if v is not a valid vertex
//    */
//   Iterable<Edge<E>> incomingEdges(Vertex<V> v) throws IllegalArgumentException;
// 
//   /** Returns the edge from u to v, or null if they are not adjacent. */
//   Edge<E> getEdge(Vertex<V> u, Vertex<V> v) throws IllegalArgumentException;
// 
//   /**
//    * Returns the vertices of edge e as an array of length two.
//    * If the graph is directed, the first vertex is the origin, and
//    * the second is the destination.  If the graph is undirected, the
//    * order is arbitrary.
//    */
//   Vertex<V>[] endVertices(Edge<E> e) throws IllegalArgumentException;
// 
//   /** Returns the vertex that is opposite vertex v on edge e. */
//   Vertex<V> opposite(Vertex<V> v, Edge<E> e) throws IllegalArgumentException;
// 
//   /** Inserts and returns a new vertex with the given element. */
//   Vertex<V> insertVertex(V element);
// 
//   /**
//    * Inserts and returns a new edge between vertices u and v, storing given element.
//    *
//    * @throws IllegalArgumentException if u or v are invalid vertices, or if an edge already exists between u and v.
//    */
//   Edge<E> insertEdge(Vertex<V> u, Vertex<V> v, E element) throws IllegalArgumentException;
// 
//   /** Removes a vertex and all its incident edges from the graph. */
//   void removeVertex(Vertex<V> v) throws IllegalArgumentException;
// 
//   /** Removes an edge from the graph. */
//   void removeEdge(Edge<E> e) throws IllegalArgumentException;
// }
// 
// Path: Labs/resources/net/datastructures/Vertex.java
// public interface Vertex<V> {
//   /** Returns the element associated with the vertex. */
//   V getElement();
// }


import net.datastructures.Edge;
import net.datastructures.Graph;
import net.datastructures.Vertex;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Hashtable;
import java.util.StringTokenizer;
// $Id: SimpleGraph.java,v 1.1 2006/11/11 03:16:10 jlang Exp $
// CSI2110 Fall 2006 Laboratory 9: Adjacency List and DFS
// ==========================================================================
// (C)opyright:
//
//   Jochen Lang
//   SITE, University of Ottawa
//   800 King Edward Ave.
//   Ottawa, On., K1N 6N5
//   Canada. 
//   http://www.site.uottawa.ca
// 
// Creator: jlang (Jochen Lang)
// Email:   jlang@site.uottawa.ca
// ==========================================================================
// $Log: SimpleGraphDFS.java,v $
// Revision 1.1  2006/11/11 03:16:10  jlang
// Added Lab9
// Modified by Lachlan Plant 2015/11/18
// Modified by Lucia Moura 2015/11/25
//
// ==========================================================================



public class SimpleGraphDijkstra {

  Graph<String,String> sGraph;  
  

  /** 
   * Create a SimpleGraph from file
   */
  public SimpleGraphDijkstra( String fileName )
    throws Exception {
    sGraph = new AdjacencyListGraph<>(false);
    read( fileName );
  }


  /**
   * Read a list of edges from file
   */
  protected void read( String fileName ) 
    throws Exception {
    BufferedReader graphFile = 
      new BufferedReader( new FileReader(fileName));
    
// Path: Labs/resources/net/datastructures/Edge.java
// public interface Edge<E> {
//   /** Returns the element associated with the edge. */
//   E getElement();
// }
// 
// Path: Labs/resources/net/datastructures/Graph.java
// public interface Graph<V,E> {
// 
//   /** Returns the number of vertices of the graph */
//   int numVertices();
// 
//   /** Returns the number of edges of the graph */
//   int numEdges();
// 
//   /** Returns the vertices of the graph as an iterable collection */
//   Iterable<Vertex<V>> vertices();
// 
//   /** Returns the edges of the graph as an iterable collection */
//   Iterable<Edge<E>> edges();
// 
//   /**
//    * Returns the number of edges leaving vertex v.
//    * Note that for an undirected graph, this is the same result
//    * returned by inDegree
//    * @throws IllegalArgumentException if v is not a valid vertex
//    */
//   int outDegree(Vertex<V> v) throws IllegalArgumentException;
// 
//   /**
//    * Returns the number of edges for which vertex v is the destination.
//    * Note that for an undirected graph, this is the same result
//    * returned by outDegree
//    * @throws IllegalArgumentException if v is not a valid vertex
//    */
//   int inDegree(Vertex<V> v) throws IllegalArgumentException;
// 
//   /**
//    * Returns an iterable collection of edges for which vertex v is the origin.
//    * Note that for an undirected graph, this is the same result
//    * returned by incomingEdges.
//    * @throws IllegalArgumentException if v is not a valid vertex
//    */
//   Iterable<Edge<E>> outgoingEdges(Vertex<V> v) throws IllegalArgumentException;
// 
//   /**
//    * Returns an iterable collection of edges for which vertex v is the destination.
//    * Note that for an undirected graph, this is the same result
//    * returned by outgoingEdges.
//    * @throws IllegalArgumentException if v is not a valid vertex
//    */
//   Iterable<Edge<E>> incomingEdges(Vertex<V> v) throws IllegalArgumentException;
// 
//   /** Returns the edge from u to v, or null if they are not adjacent. */
//   Edge<E> getEdge(Vertex<V> u, Vertex<V> v) throws IllegalArgumentException;
// 
//   /**
//    * Returns the vertices of edge e as an array of length two.
//    * If the graph is directed, the first vertex is the origin, and
//    * the second is the destination.  If the graph is undirected, the
//    * order is arbitrary.
//    */
//   Vertex<V>[] endVertices(Edge<E> e) throws IllegalArgumentException;
// 
//   /** Returns the vertex that is opposite vertex v on edge e. */
//   Vertex<V> opposite(Vertex<V> v, Edge<E> e) throws IllegalArgumentException;
// 
//   /** Inserts and returns a new vertex with the given element. */
//   Vertex<V> insertVertex(V element);
// 
//   /**
//    * Inserts and returns a new edge between vertices u and v, storing given element.
//    *
//    * @throws IllegalArgumentException if u or v are invalid vertices, or if an edge already exists between u and v.
//    */
//   Edge<E> insertEdge(Vertex<V> u, Vertex<V> v, E element) throws IllegalArgumentException;
// 
//   /** Removes a vertex and all its incident edges from the graph. */
//   void removeVertex(Vertex<V> v) throws IllegalArgumentException;
// 
//   /** Removes an edge from the graph. */
//   void removeEdge(Edge<E> e) throws IllegalArgumentException;
// }
// 
// Path: Labs/resources/net/datastructures/Vertex.java
// public interface Vertex<V> {
//   /** Returns the element associated with the vertex. */
//   V getElement();
// }


// Path: Assignments/Assignment 5/SimpleGraphDijkstra.java
import net.datastructures.Edge;
import net.datastructures.Graph;
import net.datastructures.Vertex;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Hashtable;
import java.util.StringTokenizer;

// $Id: SimpleGraph.java,v 1.1 2006/11/11 03:16:10 jlang Exp $
// CSI2110 Fall 2006 Laboratory 9: Adjacency List and DFS
// ==========================================================================
// (C)opyright:
//
//   Jochen Lang
//   SITE, University of Ottawa
//   800 King Edward Ave.
//   Ottawa, On., K1N 6N5
//   Canada. 
//   http://www.site.uottawa.ca
// 
// Creator: jlang (Jochen Lang)
// Email:   jlang@site.uottawa.ca
// ==========================================================================
// $Log: SimpleGraphDFS.java,v $
// Revision 1.1  2006/11/11 03:16:10  jlang
// Added Lab9
// Modified by Lachlan Plant 2015/11/18
// Modified by Lucia Moura 2015/11/25
//
// ==========================================================================



public class SimpleGraphDijkstra {

  Graph<String,String> sGraph;  
  

  /** 
   * Create a SimpleGraph from file
   */
  public SimpleGraphDijkstra( String fileName )
    throws Exception {
    sGraph = new AdjacencyListGraph<>(false);
    read( fileName );
  }


  /**
   * Read a list of edges from file
   */
  protected void read( String fileName ) 
    throws Exception {
    BufferedReader graphFile = 
      new BufferedReader( new FileReader(fileName));
    
    Hashtable<String,Vertex> vertices = new Hashtable<>();