The Dijkstra algorithm actually does more than just finding a shortest path from a start vertex to a destination vertex. The algorithm actually computes the shortest paths from the start vertex to every other vertex in the graph.

The first step in the Dijkstra algorithm is to add two new member variables to the Vertex class, d and previous. d is used to record the length of the shortest path found so far to that vertex, while previous is the last Vertex on the path leading to the given Vertex. At the start of the algorithm, we set the d value for the start vertex to 0 and the previous value for the start vertex to the start vertex itself. For every other vertex in the graph, we set the d value to a very large number and the previous value to null.

The last part of the initialization phase of the algorithm is to place every vertex in the graph in a set, called the pending set.

The basic step in the algorithm is an operation called relaxation that gets applied to edges. Suppose we have an edge running from vertex u to vertex v and the weight of the edge is w. The relaxation operation does the following:

if(u.d + w < v.d) { vd = ud + w; v.previous = u; }

After the initialization step, the algorithm runs the following loop:

while(the pending set is not empty) { let v = the vertex in the pending set with the smallest d value remove v from the pending set for every edge e running from v: if e runs to a vertex that is still in the pending set: relax e } 

At the end of the loop the algorithm will have computed the lowest possible d value for every vertex in the graph. The set of previous links discovered by the algorithm will form a network of shortest paths running backward from every vertex in the graph to the source vertex. To find a shortest path to any given destination, we follow the previous links from that destination back to the source, making a record of all the vertices we pass along the way. When we reach the source vertex, we can reverse that list to see the list of vertices you would have to travel through to get from the source to the destination along the shortest path.

Complete the runDjikstra and cityInGraph method given the Edge and Vertex classes. To iterate over the vertices in the vertices map and the pending set, you can use an enhanced for loop that looks like:

for(Vertex v : vertices.values())

The classes are as follows:

Edge Class:

package graph;

public class Edge { private Vertex destination; private int weight; public Edge(Vertex destination,int weight) { this.destination = destination; this.weight = weight; } public Vertex getDestination() { return destination; } public int getWeight() { return weight; } }

Vertex Class:

package graph;

import java.util.ArrayList;

public class Vertex { private String city; private ArrayList edges; public Vertex(String name) { this.city = name; edges = new ArrayList(); } public void addEdge(Vertex destination,int weight) { Edge newEdge = new Edge(destination,weight); edges.add(newEdge); } public String getName() { return city; } public Edge[] getEdges() { Edge[] result = new Edge[edges.size()]; return edges.toArray(result); } }

Graph Class:

package graph;

import java.io.File; import java.util.Scanner; import java.util.TreeMap;

public class Graph {

private TreeMap vertices;

public Graph() { vertices = new TreeMap(); }

public void readFrom(String fileName) { Scanner input = null; try { input = new Scanner(new File(fileName)); } catch (Exception ex) { ex.printStackTrace(); System.exit(-1); }

while (input.hasNext()) { String from = input.next(); String to = input.next(); int distance = input.nextInt();

Vertex fromV = null; if (!vertices.containsKey(from)) { fromV = new Vertex(from); vertices.put(from, fromV); } else { fromV = vertices.get(from); }

Vertex toV = null; if (!vertices.containsKey(to)) { toV = new Vertex(to); vertices.put(to, toV); } else { toV = vertices.get(to); }

fromV.addEdge(toV, distance); toV.addEdge(fromV, distance); } }

public Edge[] getEdgesFrom(String name) { Vertex v = vertices.get(name); if (v != null) { return v.getEdges(); } else { return new Edge[0]; } }

public static void main(String[] args) { Graph G = new Graph(); G.readFrom("highways.txt");

Scanner input = new Scanner(System.in); System.out.print("Enter the name of a start city: "); String source = input.next(); while(!G.cityInGraph(source)) { System.out.println(source+" is not a valid city."); System.out.print("Enter the name of a start city: "); source = input.next(); } System.out.print("Enter the name of a destination city: "); String destination = input.next(); while(!G.cityInGraph(destination)) { System.out.println(destination+" is not a valid city."); System.out.print("Enter the name of a destination city: "); destination = input.next(); } G.runDijkstra(source); System.out.println("Here is the path from "+source+" to "+destination+":"); G.printPath(source,destination); }

}

The task is to create and complete the runDjikstra and cityInGraph methods