You will be writing a program that computes the shortest path between two cities
ID: 642415 • Letter: Y
Question
You will be writing a program that computes the shortest path between two cities. Consider the map of the USA below. This map shows a (small) group of fights between major US cities. Each dot is a major US city. Each line is a connection between two cities. Each line also has a numeric value, representing the (approximate) flight time of a journey between the two connected cities. For example, the map below shows that a flight between Seattle, WA and Chicago, IL will take approximately 3 hours.
We can abstract the connections above off the diagram of the map into a mathematical structure known as a graph. Below is a graph model of the flight connections given above. Note that it is exactly like the model above, except that we no longer have the map underneath the cities and paths. In this model, each "dot" is known as a node. Two nodes are said to be adjacent to each other if there is a path connecting them. (So the nodes representing Seattle and Chicago are adjacent according to this defintion).
We can store information about a graph in a structure known as an adjacency list. In an adjacency list, each node has an associated list of adjacent nodes. For example, the adjacency list for the above graph (assuming that each node is named after the city is represents) would be:
Atlanta: StLouis, Dallas, Miami
Boston: Chicago, NewYork
Chicago: Columbus, NewYork, Boston, StLouis, Denver, Seattle
Columbus: Chicago, Miami
Dallas: StLouis, Atlanta, Miami, LosAngeles
Denver: Chicago, SanFrancisco, LasVegas, Seattle
LasVegas: LosAngeles, SanFrancisco, Denver
LosAngeles: Dallas, SanFrancisco, LasVegas
Miami: Columbus, Atlanta, Dallas
NewYork: Chicago, Boston
SanFrancisco: LosAngeles, LasVegas, Seattle, Denver
Seattle: Chicago, SanFrancisco, Denver
StLouis: Chicago, Atlanta, Dallas
The adjacency list can be augmented with path costs. In this case, the list contains both the name of the node and the path cost from the start node to that node:
Atlanta: (StLouis:1.0), (Dallas:1.0), (Miami:1.0)
Boston: (Chicago:2.0), (NewYork:0.5)
Chicago: (Columbus:0.5), (NewYork:1.5), (Boston:2.0), (StLouis:0.5), (Denver:2.5), (Seattle:3.0)
Columbus: (Chicago:0.5), (Miami:2.0)
Dallas: (StLouis:1.0), (Atlanta:1.0), (Miami:2.0), (LosAngeles:2.5)
Denver: (Chicago:2.5), (SanFrancisco:2.0), (LasVegas:1.0), (Seattle:2.0)
LasVegas: (LosAngeles:0.5), (SanFrancisco:1.0), (Denver:1.0)
LosAngeles: (Dallas:2.5), (SanFrancisco:1.0), (LasVegas:0.5)
Miami: (Columbus:2.0), (Atlanta:1.0), (Dallas:2.0)
NewYork: (Chicago:1.5), (Boston:0.5)
SanFrancisco: (LosAngeles:1.0), (LasVegas:1.0), (Seattle:2.0), (Denver:2.0)
Seattle: (Chicago:3.0), (SanFrancisco:2.0), (Denver:2.0)
StLouis: (Chicago:0.5), (Atlanta:1.0), (Dallas:1.0)
The shortest path cost between two nodes in a graph is the minimum cost it takes to get from one node to another. For example, there are many different paths between Chicago and Los Angeles. We could choose to travel from Chicago to Seattle, then to San Francisco, then to Las Vegas and finally to Los Angeles. This route would have a path cost of 6.5 hours. But the shortest path cost between Chicago and Los Angeles is 4.0 hours - the path from Chicago to Denver, then to Las Vegas and then to Los Angeles. Given a graph, an algorithm for finding the shortest path cost from a start node to all of the possible terminal nodes is:
Begin with our initial location and call it start.
Assume we have a data structure for Paths. A Path has two attributes - a destination name and a path cost to that destination.
Create an empty Map<String,Double> data structure named shortestDistances. This will map names to final path costs.
Create an empty PriorityQueue of Paths. The PriorityQueue will prioritize Paths in order of path cost.
Add the Path (start:0.0) to the PriorityQueue (representing the distance from the inital node to itself, which is always 0.0).
While the PriorityQueue is not empty:
Remove the Path with the smallest path cost from the PriorityQueue and call it current.
If the name of the node in the Path current is NOT in the shortestDistances map:
Get the distance noted in the Path current. Call it d.
Get the destination name noted in the Path current. Call it dest.
Add the pair (dest, d) to the shortestDistances map. You now have the shortest distance from the initial node to that destination.
For each node/path cost pair n in the adjacency list of the node destination:
Add a path to the priority queue (n.nodename, d + n.pathcost)
When the PriorityQueue is empty, the Map shortestDistances contains the shortest distance between your start location and every other location in the graph
Implement this algorithm for a graph like the one above. It is IMPORTANT that you work through each section step by step - do not try to jump right to coding this algorithm all at once. Get each piece working in turn before you move onto the next piece.
Create a new Project folder named Project05 and a new program named Project05.java
Before you start any coding for this project, make sure you understand the algorithm that is outlined above. Using the adjacency list above, follow the instructions for computing the shortest distance from Columbus to all of the nodes in the graph by hand in a plain text file. Show the intial setup, and each iteration of the algorithm. Show your PriorityQueue as a sorted list of paths.
As an example, here are the intial setup and first few steps showing this algorithm starting from Seattle. You should do something similar for Columbus:
Initial Setup
=============
shortestDistances: empty
PriorityQueue: (Seattle:0.0)
After Iteration 0
=================
shortestDistances: {Seattle:0.0}
PriorityQueue: (San Francisco:2.0), (Denver:2.0), (Chicago:3.0)
After Iteration 1
=================
shortestDistances: {Seattle:0.0}, {San Francisco:2.0}
PriorityQueue: (Denver:2.0), (Chicago:3.0), (Los Angeles:3.0), (Las Vegas:3.0), (Seattle:4.0), (Denver:4.0)
After Iteration 2
=================
shortestDistances: {Seattle:0.0}, {San Francisco:2.0}, {Denver:2.0}
PriorityQueue: (Chicago:3.0), (Los Angeles:3.0), (Las Vegas:3.0), (Las Vegas:3.0), (Seattle:4.0), (Denver:4.0), (San Francisco:4.0), (Seattle:4.0), (Chicago:4.5), (Las Vegas:5.0)
etc.
Your text file should show the complete algorithm starting in Columbus and running until the priority queue is empty. Notice that with this basic algorithm only the first encounter with each city is added to the shortest distance map (since the way the priority queue works the first one you encounter will have the shortest distance).
Note that for this assignment we need a few pieces. We need to have a Path class that stores distances, we need to somehow build an adjacency list, and then we need to implement the algorithm described above. The Path class is provided for you below
Explanation / Answer
Given below is the code for the question.
Graph.java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;
public class Graph {
class Node
{
String name;
ArrayList<Edge> edges;
Node(String n)
{
name = n;
edges = new ArrayList<Edge>();
}
boolean hasEdge(String toNode)
{
for(Edge e : edges)
if(e.toNode.equalsIgnoreCase(toNode))
return true;
return false;
}
}
class Edge
{
String toNode;
double cost;
Edge(String to, double c)
{
toNode = to;
cost = c;
}
public String toString()
{
return "(" + toNode + ": " + cost + ")";
}
}
class Path
{
String destination;
double cost;
Path(String dest, double c)
{
destination = dest;
cost = c;
}
public String toString()
{
return "(" + destination + ": " + cost + ")";
}
}
HashMap<String, Node> nodes;
public Graph()
{
nodes = new HashMap<String, Node>();
}
public void addNode(String name)
{
if(nodes.get(name) == null)
{
nodes.put(name, new Node(name));
}
}
public void addEdge(String source, String dest, double cost)
{
Node n1 = nodes.get(source);
Node n2 = nodes.get(dest);
if(n1 != null && n2 != null)
{
if(!n1.hasEdge(dest))
n1.edges.add(new Edge(dest, cost));
if(!n2.hasEdge(source))
n2.edges.add(new Edge(source, cost));
}
}
public void display()
{
for(String k : nodes.keySet())
{
System.out.print(k +": " );
for(Edge e : nodes.get(k).edges)
System.out.print(e + " ");
System.out.println();
}
System.out.println();
}
public void shortestPath(String start)
{
HashMap<String, Double> shortestDistances = new HashMap<String, Double>();
PriorityQueue<Path> queue = new PriorityQueue<Path>(new Comparator<Path>() {
@Override
public int compare(Path o1, Path o2) {
if(o1.cost < o2.cost)
return -1;
else if(o1.cost == o2.cost)
return 0;
else
return 1;
}
});
queue.add(new Path(start, 0));
System.out.println("Initial Setup");
System.out.println("===============");
System.out.println("shortestDistances: " + shortestDistances.toString());
System.out.println("PriorityQueue: " + queue.toString());
int iteration = 0;
while(!queue.isEmpty())
{
Path current = queue.remove();
if(!shortestDistances.containsKey(current.destination))
{
double d = current.cost;
String dest = current.destination;
shortestDistances.put(dest, d);
for(Edge e : nodes.get(dest).edges)
{
queue.add(new Path(e.toNode, d + e.cost));
}
}
System.out.println("After Iteration " + iteration);
System.out.println("===============");
System.out.println("shortestDistances: " + shortestDistances.toString());
System.out.println("PriorityQueue: " + queue.toString());
iteration++;
}
}
}
GraphTest.java
public class GraphTest {
public static void main(String[] args) {
Graph g = new Graph();
g.addNode("Atlanta");
g.addNode("Boston");
g.addNode("Chicago");
g.addNode("Columbus");
g.addNode("Dallas");
g.addNode("Denver");
g.addNode("LasVegas");
g.addNode("LosAngeles");
g.addNode("Miami");
g.addNode("NewYork");
g.addNode("SanFrancisco");
g.addNode("Seattle");
g.addNode("StLouis");
g.addEdge("Atlanta", "StLouis", 1 );
g.addEdge("Atlanta", "Dallas", 1 );
g.addEdge("Atlanta", "Miami", 1 );
g.addEdge("Boston", "Chicago", 2);
g.addEdge("Boston", "NewYork", 0.5);
g.addEdge("Chicago", "Columbus", 0.5);
g.addEdge("Chicago", "NewYork", 1.5);
g.addEdge("Chicago", "StLouis", 0.5);
g.addEdge("Chicago", "Denver", 2.5);
g.addEdge("Chicago", "Seattle", 3 );
g.addEdge("Columbus", "Miami", 2 );
g.addEdge("Dallas", "StLouis", 1);
g.addEdge("Dallas", "Miami", 2 );
g.addEdge("Dallas", "LosAngeles", 2.5 );
g.addEdge("Denver", "SanFrancisco", 2 );
g.addEdge("Denver", "LasVegas", 1 );
g.addEdge("Denver", "Seattle", 2 );
g.addEdge("LasVegas", "LosAngeles", 0.5 );
g.addEdge("LasVegas", "SanFrancisco", 1);
g.addEdge("LosAngeles", "SanFrancisco",1 );
g.addEdge("SanFrancisco", "Seattle", 2);
g.display();
g.shortestPath("Seattle");
}
}
output
SanFrancisco: (Denver: 2.0) (LasVegas: 1.0) (LosAngeles: 1.0) (Seattle: 2.0)
StLouis: (Atlanta: 1.0) (Chicago: 0.5) (Dallas: 1.0)
Seattle: (Chicago: 3.0) (Denver: 2.0) (SanFrancisco: 2.0)
Chicago: (Boston: 2.0) (Columbus: 0.5) (NewYork: 1.5) (StLouis: 0.5) (Denver: 2.5) (Seattle: 3.0)
Miami: (Atlanta: 1.0) (Columbus: 2.0) (Dallas: 2.0)
LasVegas: (Denver: 1.0) (LosAngeles: 0.5) (SanFrancisco: 1.0)
Atlanta: (StLouis: 1.0) (Dallas: 1.0) (Miami: 1.0)
Columbus: (Chicago: 0.5) (Miami: 2.0)
NewYork: (Boston: 0.5) (Chicago: 1.5)
Denver: (Chicago: 2.5) (SanFrancisco: 2.0) (LasVegas: 1.0) (Seattle: 2.0)
LosAngeles: (Dallas: 2.5) (LasVegas: 0.5) (SanFrancisco: 1.0)
Dallas: (Atlanta: 1.0) (StLouis: 1.0) (Miami: 2.0) (LosAngeles: 2.5)
Boston: (Chicago: 2.0) (NewYork: 0.5)
Initial Setup
===============
shortestDistances: {}
PriorityQueue: [(Seattle: 0.0)]
After Iteration 0
===============
shortestDistances: {Seattle=0.0}
PriorityQueue: [(Denver: 2.0), (Chicago: 3.0), (SanFrancisco: 2.0)]
After Iteration 1
===============
shortestDistances: {Seattle=0.0, Denver=2.0}
PriorityQueue: [(SanFrancisco: 2.0), (Chicago: 3.0), (Seattle: 4.0), (SanFrancisco: 4.0), (LasVegas: 3.0), (Chicago: 4.5)]
After Iteration 2
===============
shortestDistances: {SanFrancisco=2.0, Seattle=0.0, Denver=2.0}
PriorityQueue: [(Chicago: 3.0), (LasVegas: 3.0), (LasVegas: 3.0), (LosAngeles: 3.0), (Chicago: 4.5), (Denver: 4.0), (Seattle: 4.0), (SanFrancisco: 4.0), (Seattle: 4.0)]
After Iteration 3
===============
shortestDistances: {SanFrancisco=2.0, Seattle=0.0, Chicago=3.0, Denver=2.0}
PriorityQueue: [(LasVegas: 3.0), (LosAngeles: 3.0), (LasVegas: 3.0), (Seattle: 4.0), (Columbus: 3.5), (StLouis: 3.5), (Seattle: 4.0), (SanFrancisco: 4.0), (Boston: 5.0), (Chicago: 4.5), (NewYork: 4.5), (Denver: 4.0), (Denver: 5.5), (Seattle: 6.0)]
After Iteration 4
===============
shortestDistances: {SanFrancisco=2.0, LasVegas=3.0, Seattle=0.0, Chicago=3.0, Denver=2.0}
PriorityQueue: [(LosAngeles: 3.0), (Columbus: 3.5), (LasVegas: 3.0), (Seattle: 4.0), (Chicago: 4.5), (StLouis: 3.5), (LosAngeles: 3.5), (SanFrancisco: 4.0), (Boston: 5.0), (Seattle: 6.0), (NewYork: 4.5), (Denver: 4.0), (Denver: 5.5), (Denver: 4.0), (Seattle: 4.0), (SanFrancisco: 4.0)]
After Iteration 5
===============
shortestDistances: {SanFrancisco=2.0, LasVegas=3.0, Seattle=0.0, Chicago=3.0, Denver=2.0, LosAngeles=3.0}
PriorityQueue: [(LasVegas: 3.0), (Columbus: 3.5), (StLouis: 3.5), (LasVegas: 3.5), (Chicago: 4.5), (SanFrancisco: 4.0), (LosAngeles: 3.5), (Seattle: 4.0), (SanFrancisco: 4.0), (Seattle: 6.0), (NewYork: 4.5), (Denver: 4.0), (Denver: 5.5), (Denver: 4.0), (Seattle: 4.0), (Dallas: 5.5), (SanFrancisco: 4.0), (Boston: 5.0)]
After Iteration 6
===============
shortestDistances: {SanFrancisco=2.0, LasVegas=3.0, Seattle=0.0, Chicago=3.0, Denver=2.0, LosAngeles=3.0}
PriorityQueue: [(Columbus: 3.5), (LasVegas: 3.5), (StLouis: 3.5), (Seattle: 4.0), (Chicago: 4.5), (SanFrancisco: 4.0), (LosAngeles: 3.5), (SanFrancisco: 4.0), (SanFrancisco: 4.0), (Seattle: 6.0), (NewYork: 4.5), (Denver: 4.0), (Denver: 5.5), (Denver: 4.0), (Seattle: 4.0), (Dallas: 5.5), (Boston: 5.0)]
After Iteration 7
===============
shortestDistances: {SanFrancisco=2.0, LasVegas=3.0, Seattle=0.0, Chicago=3.0, Columbus=3.5, Denver=2.0, LosAngeles=3.0}
PriorityQueue: [(LasVegas: 3.5), (Seattle: 4.0), (StLouis: 3.5), (SanFrancisco: 4.0), (Chicago: 4.5), (SanFrancisco: 4.0), (LosAngeles: 3.5), (Chicago: 4.0), (SanFrancisco: 4.0), (Seattle: 6.0), (NewYork: 4.5), (Denver: 4.0), (Denver: 5.5), (Denver: 4.0), (Seattle: 4.0), (Dallas: 5.5), (Boston: 5.0), (Miami: 5.5)]
After Iteration 8
===============
shortestDistances: {SanFrancisco=2.0, LasVegas=3.0, Seattle=0.0, Chicago=3.0, Columbus=3.5, Denver=2.0, LosAngeles=3.0}
PriorityQueue: [(StLouis: 3.5), (Seattle: 4.0), (LosAngeles: 3.5), (SanFrancisco: 4.0), (Chicago: 4.5), (SanFrancisco: 4.0), (Denver: 4.0), (Chicago: 4.0), (SanFrancisco: 4.0), (Seattle: 6.0), (NewYork: 4.5), (Denver: 4.0), (Denver: 5.5), (Miami: 5.5), (Seattle: 4.0), (Dallas: 5.5), (Boston: 5.0)]
After Iteration 9
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, LasVegas=3.0, Seattle=0.0, Chicago=3.0, Columbus=3.5, Denver=2.0, LosAngeles=3.0}
PriorityQueue: [(LosAngeles: 3.5), (Seattle: 4.0), (SanFrancisco: 4.0), (SanFrancisco: 4.0), (Chicago: 4.5), (Denver: 4.0), (Denver: 4.0), (Chicago: 4.0), (SanFrancisco: 4.0), (Seattle: 6.0), (NewYork: 4.5), (Boston: 5.0), (Denver: 5.5), (Miami: 5.5), (Seattle: 4.0), (Dallas: 5.5), (Atlanta: 4.5), (Chicago: 4.0), (Dallas: 4.5)]
After Iteration 10
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, LasVegas=3.0, Seattle=0.0, Chicago=3.0, Columbus=3.5, Denver=2.0, LosAngeles=3.0}
PriorityQueue: [(Seattle: 4.0), (SanFrancisco: 4.0), (SanFrancisco: 4.0), (Chicago: 4.0), (Chicago: 4.5), (Denver: 4.0), (Denver: 4.0), (Dallas: 4.5), (SanFrancisco: 4.0), (Seattle: 6.0), (NewYork: 4.5), (Boston: 5.0), (Denver: 5.5), (Miami: 5.5), (Seattle: 4.0), (Dallas: 5.5), (Atlanta: 4.5), (Chicago: 4.0)]
After Iteration 11
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, LasVegas=3.0, Seattle=0.0, Chicago=3.0, Columbus=3.5, Denver=2.0, LosAngeles=3.0}
PriorityQueue: [(Chicago: 4.0), (SanFrancisco: 4.0), (SanFrancisco: 4.0), (Chicago: 4.0), (Chicago: 4.5), (Denver: 4.0), (Denver: 4.0), (Dallas: 4.5), (SanFrancisco: 4.0), (Seattle: 6.0), (NewYork: 4.5), (Boston: 5.0), (Denver: 5.5), (Miami: 5.5), (Seattle: 4.0), (Dallas: 5.5), (Atlanta: 4.5)]
After Iteration 12
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, LasVegas=3.0, Seattle=0.0, Chicago=3.0, Columbus=3.5, Denver=2.0, LosAngeles=3.0}
PriorityQueue: [(SanFrancisco: 4.0), (Chicago: 4.0), (SanFrancisco: 4.0), (SanFrancisco: 4.0), (Chicago: 4.5), (Denver: 4.0), (Denver: 4.0), (Dallas: 4.5), (Atlanta: 4.5), (Seattle: 6.0), (NewYork: 4.5), (Boston: 5.0), (Denver: 5.5), (Miami: 5.5), (Seattle: 4.0), (Dallas: 5.5)]
After Iteration 13
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, LasVegas=3.0, Seattle=0.0, Chicago=3.0, Columbus=3.5, Denver=2.0, LosAngeles=3.0}
PriorityQueue: [(Chicago: 4.0), (SanFrancisco: 4.0), (SanFrancisco: 4.0), (Dallas: 4.5), (Chicago: 4.5), (Denver: 4.0), (Denver: 4.0), (Dallas: 5.5), (Atlanta: 4.5), (Seattle: 6.0), (NewYork: 4.5), (Boston: 5.0), (Denver: 5.5), (Miami: 5.5), (Seattle: 4.0)]
After Iteration 14
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, LasVegas=3.0, Seattle=0.0, Chicago=3.0, Columbus=3.5, Denver=2.0, LosAngeles=3.0}
PriorityQueue: [(Seattle: 4.0), (SanFrancisco: 4.0), (SanFrancisco: 4.0), (Dallas: 4.5), (Chicago: 4.5), (Denver: 4.0), (Denver: 4.0), (Dallas: 5.5), (Atlanta: 4.5), (Seattle: 6.0), (NewYork: 4.5), (Boston: 5.0), (Denver: 5.5), (Miami: 5.5)]
After Iteration 15
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, LasVegas=3.0, Seattle=0.0, Chicago=3.0, Columbus=3.5, Denver=2.0, LosAngeles=3.0}
PriorityQueue: [(SanFrancisco: 4.0), (Dallas: 4.5), (SanFrancisco: 4.0), (Atlanta: 4.5), (Chicago: 4.5), (Denver: 4.0), (Denver: 4.0), (Dallas: 5.5), (Miami: 5.5), (Seattle: 6.0), (NewYork: 4.5), (Boston: 5.0), (Denver: 5.5)]
After Iteration 16
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, LasVegas=3.0, Seattle=0.0, Chicago=3.0, Columbus=3.5, Denver=2.0, LosAngeles=3.0}
PriorityQueue: [(SanFrancisco: 4.0), (Dallas: 4.5), (Denver: 4.0), (Atlanta: 4.5), (Chicago: 4.5), (Boston: 5.0), (Denver: 4.0), (Dallas: 5.5), (Miami: 5.5), (Seattle: 6.0), (NewYork: 4.5), (Denver: 5.5)]
After Iteration 17
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, LasVegas=3.0, Seattle=0.0, Chicago=3.0, Columbus=3.5, Denver=2.0, LosAngeles=3.0}
PriorityQueue: [(Denver: 4.0), (Dallas: 4.5), (Denver: 4.0), (Atlanta: 4.5), (Chicago: 4.5), (Boston: 5.0), (Denver: 5.5), (Dallas: 5.5), (Miami: 5.5), (Seattle: 6.0), (NewYork: 4.5)]
After Iteration 18
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, LasVegas=3.0, Seattle=0.0, Chicago=3.0, Columbus=3.5, Denver=2.0, LosAngeles=3.0}
PriorityQueue: [(Denver: 4.0), (Dallas: 4.5), (NewYork: 4.5), (Atlanta: 4.5), (Chicago: 4.5), (Boston: 5.0), (Denver: 5.5), (Dallas: 5.5), (Miami: 5.5), (Seattle: 6.0)]
After Iteration 19
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, LasVegas=3.0, Seattle=0.0, Chicago=3.0, Columbus=3.5, Denver=2.0, LosAngeles=3.0}
PriorityQueue: [(Dallas: 4.5), (Atlanta: 4.5), (NewYork: 4.5), (Dallas: 5.5), (Chicago: 4.5), (Boston: 5.0), (Denver: 5.5), (Seattle: 6.0), (Miami: 5.5)]
After Iteration 20
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, LasVegas=3.0, Seattle=0.0, Chicago=3.0, Columbus=3.5, Denver=2.0, LosAngeles=3.0, Dallas=4.5}
PriorityQueue: [(Atlanta: 4.5), (Chicago: 4.5), (NewYork: 4.5), (Dallas: 5.5), (Miami: 5.5), (Boston: 5.0), (Denver: 5.5), (Seattle: 6.0), (Atlanta: 5.5), (StLouis: 5.5), (Miami: 6.5), (LosAngeles: 7.0)]
After Iteration 21
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, LasVegas=3.0, Seattle=0.0, Chicago=3.0, Atlanta=4.5, Columbus=3.5, Denver=2.0, LosAngeles=3.0, Dallas=4.5}
PriorityQueue: [(Chicago: 4.5), (Dallas: 5.5), (NewYork: 4.5), (Atlanta: 5.5), (Miami: 5.5), (Boston: 5.0), (Denver: 5.5), (Seattle: 6.0), (LosAngeles: 7.0), (StLouis: 5.5), (Miami: 6.5), (StLouis: 5.5), (Dallas: 5.5), (Miami: 5.5)]
After Iteration 22
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, LasVegas=3.0, Seattle=0.0, Chicago=3.0, Atlanta=4.5, Columbus=3.5, Denver=2.0, LosAngeles=3.0, Dallas=4.5}
PriorityQueue: [(NewYork: 4.5), (Dallas: 5.5), (Boston: 5.0), (Atlanta: 5.5), (Miami: 5.5), (Miami: 5.5), (Denver: 5.5), (Seattle: 6.0), (LosAngeles: 7.0), (StLouis: 5.5), (Miami: 6.5), (StLouis: 5.5), (Dallas: 5.5)]
After Iteration 23
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, LasVegas=3.0, Seattle=0.0, Chicago=3.0, Atlanta=4.5, Columbus=3.5, NewYork=4.5, Denver=2.0, LosAngeles=3.0, Dallas=4.5}
PriorityQueue: [(Boston: 5.0), (Dallas: 5.5), (Boston: 5.0), (Atlanta: 5.5), (Miami: 5.5), (Dallas: 5.5), (Denver: 5.5), (Seattle: 6.0), (LosAngeles: 7.0), (StLouis: 5.5), (Miami: 6.5), (StLouis: 5.5), (Miami: 5.5), (Chicago: 6.0)]
After Iteration 24
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, LasVegas=3.0, Seattle=0.0, Chicago=3.0, Atlanta=4.5, Columbus=3.5, NewYork=4.5, Denver=2.0, LosAngeles=3.0, Dallas=4.5, Boston=5.0}
PriorityQueue: [(Boston: 5.0), (Dallas: 5.5), (Dallas: 5.5), (Atlanta: 5.5), (Miami: 5.5), (StLouis: 5.5), (Denver: 5.5), (Seattle: 6.0), (LosAngeles: 7.0), (StLouis: 5.5), (Miami: 6.5), (Chicago: 6.0), (Miami: 5.5), (Chicago: 7.0), (NewYork: 5.5)]
After Iteration 25
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, LasVegas=3.0, Seattle=0.0, Chicago=3.0, Atlanta=4.5, Columbus=3.5, NewYork=4.5, Denver=2.0, LosAngeles=3.0, Dallas=4.5, Boston=5.0}
PriorityQueue: [(NewYork: 5.5), (Dallas: 5.5), (Dallas: 5.5), (Atlanta: 5.5), (Miami: 5.5), (StLouis: 5.5), (Denver: 5.5), (Seattle: 6.0), (LosAngeles: 7.0), (StLouis: 5.5), (Miami: 6.5), (Chicago: 6.0), (Miami: 5.5), (Chicago: 7.0)]
After Iteration 26
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, LasVegas=3.0, Seattle=0.0, Chicago=3.0, Atlanta=4.5, Columbus=3.5, NewYork=4.5, Denver=2.0, LosAngeles=3.0, Dallas=4.5, Boston=5.0}
PriorityQueue: [(Dallas: 5.5), (Atlanta: 5.5), (Dallas: 5.5), (Seattle: 6.0), (Miami: 5.5), (StLouis: 5.5), (Denver: 5.5), (Chicago: 7.0), (LosAngeles: 7.0), (StLouis: 5.5), (Miami: 6.5), (Chicago: 6.0), (Miami: 5.5)]
After Iteration 27
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, LasVegas=3.0, Seattle=0.0, Chicago=3.0, Atlanta=4.5, Columbus=3.5, NewYork=4.5, Denver=2.0, LosAngeles=3.0, Dallas=4.5, Boston=5.0}
PriorityQueue: [(Miami: 5.5), (Atlanta: 5.5), (Dallas: 5.5), (Seattle: 6.0), (Miami: 5.5), (StLouis: 5.5), (Denver: 5.5), (Chicago: 7.0), (LosAngeles: 7.0), (StLouis: 5.5), (Miami: 6.5), (Chicago: 6.0)]
After Iteration 28
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, Seattle=0.0, Chicago=3.0, Miami=5.5, LasVegas=3.0, Atlanta=4.5, Columbus=3.5, NewYork=4.5, Denver=2.0, LosAngeles=3.0, Dallas=4.5, Boston=5.0}
PriorityQueue: [(Atlanta: 5.5), (Miami: 5.5), (Dallas: 5.5), (Seattle: 6.0), (StLouis: 5.5), (StLouis: 5.5), (Denver: 5.5), (Chicago: 7.0), (LosAngeles: 7.0), (Chicago: 6.0), (Miami: 6.5), (Atlanta: 6.5), (Columbus: 7.5), (Dallas: 7.5)]
After Iteration 29
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, Seattle=0.0, Chicago=3.0, Miami=5.5, LasVegas=3.0, Atlanta=4.5, Columbus=3.5, NewYork=4.5, Denver=2.0, LosAngeles=3.0, Dallas=4.5, Boston=5.0}
PriorityQueue: [(Miami: 5.5), (StLouis: 5.5), (Dallas: 5.5), (Seattle: 6.0), (Chicago: 6.0), (StLouis: 5.5), (Denver: 5.5), (Chicago: 7.0), (LosAngeles: 7.0), (Dallas: 7.5), (Miami: 6.5), (Atlanta: 6.5), (Columbus: 7.5)]
After Iteration 30
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, Seattle=0.0, Chicago=3.0, Miami=5.5, LasVegas=3.0, Atlanta=4.5, Columbus=3.5, NewYork=4.5, Denver=2.0, LosAngeles=3.0, Dallas=4.5, Boston=5.0}
PriorityQueue: [(StLouis: 5.5), (Seattle: 6.0), (Dallas: 5.5), (Chicago: 7.0), (Chicago: 6.0), (StLouis: 5.5), (Denver: 5.5), (Columbus: 7.5), (LosAngeles: 7.0), (Dallas: 7.5), (Miami: 6.5), (Atlanta: 6.5)]
After Iteration 31
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, Seattle=0.0, Chicago=3.0, Miami=5.5, LasVegas=3.0, Atlanta=4.5, Columbus=3.5, NewYork=4.5, Denver=2.0, LosAngeles=3.0, Dallas=4.5, Boston=5.0}
PriorityQueue: [(Dallas: 5.5), (Seattle: 6.0), (StLouis: 5.5), (Chicago: 7.0), (Chicago: 6.0), (Atlanta: 6.5), (Denver: 5.5), (Columbus: 7.5), (LosAngeles: 7.0), (Dallas: 7.5), (Miami: 6.5)]
After Iteration 32
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, Seattle=0.0, Chicago=3.0, Miami=5.5, LasVegas=3.0, Atlanta=4.5, Columbus=3.5, NewYork=4.5, Denver=2.0, LosAngeles=3.0, Dallas=4.5, Boston=5.0}
PriorityQueue: [(StLouis: 5.5), (Seattle: 6.0), (Denver: 5.5), (Chicago: 7.0), (Chicago: 6.0), (Atlanta: 6.5), (Miami: 6.5), (Columbus: 7.5), (LosAngeles: 7.0), (Dallas: 7.5)]
After Iteration 33
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, Seattle=0.0, Chicago=3.0, Miami=5.5, LasVegas=3.0, Atlanta=4.5, Columbus=3.5, NewYork=4.5, Denver=2.0, LosAngeles=3.0, Dallas=4.5, Boston=5.0}
PriorityQueue: [(Denver: 5.5), (Seattle: 6.0), (Atlanta: 6.5), (Chicago: 7.0), (Chicago: 6.0), (Dallas: 7.5), (Miami: 6.5), (Columbus: 7.5), (LosAngeles: 7.0)]
After Iteration 34
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, Seattle=0.0, Chicago=3.0, Miami=5.5, LasVegas=3.0, Atlanta=4.5, Columbus=3.5, NewYork=4.5, Denver=2.0, LosAngeles=3.0, Dallas=4.5, Boston=5.0}
PriorityQueue: [(Seattle: 6.0), (Chicago: 6.0), (Atlanta: 6.5), (Chicago: 7.0), (LosAngeles: 7.0), (Dallas: 7.5), (Miami: 6.5), (Columbus: 7.5)]
After Iteration 35
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, Seattle=0.0, Chicago=3.0, Miami=5.5, LasVegas=3.0, Atlanta=4.5, Columbus=3.5, NewYork=4.5, Denver=2.0, LosAngeles=3.0, Dallas=4.5, Boston=5.0}
PriorityQueue: [(Chicago: 6.0), (Chicago: 7.0), (Atlanta: 6.5), (Columbus: 7.5), (LosAngeles: 7.0), (Dallas: 7.5), (Miami: 6.5)]
After Iteration 36
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, Seattle=0.0, Chicago=3.0, Miami=5.5, LasVegas=3.0, Atlanta=4.5, Columbus=3.5, NewYork=4.5, Denver=2.0, LosAngeles=3.0, Dallas=4.5, Boston=5.0}
PriorityQueue: [(Miami: 6.5), (Chicago: 7.0), (Atlanta: 6.5), (Columbus: 7.5), (LosAngeles: 7.0), (Dallas: 7.5)]
After Iteration 37
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, Seattle=0.0, Chicago=3.0, Miami=5.5, LasVegas=3.0, Atlanta=4.5, Columbus=3.5, NewYork=4.5, Denver=2.0, LosAngeles=3.0, Dallas=4.5, Boston=5.0}
PriorityQueue: [(Atlanta: 6.5), (Chicago: 7.0), (Dallas: 7.5), (Columbus: 7.5), (LosAngeles: 7.0)]
After Iteration 38
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, Seattle=0.0, Chicago=3.0, Miami=5.5, LasVegas=3.0, Atlanta=4.5, Columbus=3.5, NewYork=4.5, Denver=2.0, LosAngeles=3.0, Dallas=4.5, Boston=5.0}
PriorityQueue: [(LosAngeles: 7.0), (Chicago: 7.0), (Dallas: 7.5), (Columbus: 7.5)]
After Iteration 39
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, Seattle=0.0, Chicago=3.0, Miami=5.5, LasVegas=3.0, Atlanta=4.5, Columbus=3.5, NewYork=4.5, Denver=2.0, LosAngeles=3.0, Dallas=4.5, Boston=5.0}
PriorityQueue: [(Chicago: 7.0), (Columbus: 7.5), (Dallas: 7.5)]
After Iteration 40
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, Seattle=0.0, Chicago=3.0, Miami=5.5, LasVegas=3.0, Atlanta=4.5, Columbus=3.5, NewYork=4.5, Denver=2.0, LosAngeles=3.0, Dallas=4.5, Boston=5.0}
PriorityQueue: [(Dallas: 7.5), (Columbus: 7.5)]
After Iteration 41
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, Seattle=0.0, Chicago=3.0, Miami=5.5, LasVegas=3.0, Atlanta=4.5, Columbus=3.5, NewYork=4.5, Denver=2.0, LosAngeles=3.0, Dallas=4.5, Boston=5.0}
PriorityQueue: [(Columbus: 7.5)]
After Iteration 42
===============
shortestDistances: {SanFrancisco=2.0, StLouis=3.5, Seattle=0.0, Chicago=3.0, Miami=5.5, LasVegas=3.0, Atlanta=4.5, Columbus=3.5, NewYork=4.5, Denver=2.0, LosAngeles=3.0, Dallas=4.5, Boston=5.0}
PriorityQueue: []
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.