Implement Dijkstra’s Algorithm on a graph supporting simple integer weights. Your input will consist of a number of vertices and a list of doubly-connected edges along with their costs; your output will consist of a simple representation of the Dijkstra spanning tree.
Sample input for the graph from the slides:
6 # number of vertices5 # source vertex9 # number of edges1 2 41 5 32 3 22 4 92 5 83 4 14 5 54 6 35 6 7
Sample output for the same graph:
61 3 52 7 13 6 44 5 55 -1 -16 7 5 Dijkstra from node 4.
Visit 4:-1:-1
Find: 2:15, 3:3, 5:6, 6:8
Visited: 4:-1:-1
Queue: 2:15:4, 3:3:4, 5:6:4, 6:8:4
Visit 3:3:4
Find: 1:12, 6:7
Visited: 3:3:4, 4:-1:-1
Queue: 1:12:3, 2:15:4, 5:6:4, 6:7:3
Visit 5:6:4
Find: 2:8, 7:14
Visited: 3:3:4, 4:-1:-1, 5:6:4
Queue: 1:12:3, 2:8:5, 6:7:3, 7:14:5
Visit 6:7:3
Find: 7:24
Visited: 3:3:4, 4:-1:-1, 5:6:4, 6:7:3
Queue: 1:12:3, 2:8:5, 7:14:5
Visit 2:8:5
Find: 1:15
Visited: 2:8:5, 3:3:4, 4:-1:-1, 5:6:4, 6:7:3
Queue: 1:12:3, 7:14:5
Visits to 1:12:3 and 7:14:5 find nothing
Final: 1:12:3, 2:8:5, 3:3:4, 4:-1:-1, 5:6:4, 6:7:3, 7:14:5
7
4
10
1 2 7
1 3 9
2 4 15
2 5 2
3 4 3
3 6 4
4 5 6
4 6 8
5 7 8
6 7 16
7
1 12 3
2 8 5
3 3 4
4 -1 -1
5 6 4
6 7 3
7 14 5
Dijkstra from node 5.
Visit 5:-1:-1
Find: 2:2, 4:6, 7:8
Visited: 5:-1:-1
Queue: 2:2:5, 4:6:5, 7:8:5
Visit 2:2:5
Find: 1:9, 4:17
Visited: 2:2:5, 5:-1:-1
Queue: 1:9:2, 4:6:5, 7:8:5
Visit 4:6:5
Find: 3:9, 6:14
Visited: 2:2:5, 4:6:5, 5:-1:-1
Queue: 1:9:2, 3:9:4, 6:14:4, 7:8:5
Visit 7:8:5
Find: 6:24
Visited: 2:2:5, 4:6:5, 5:-1:-1, 7:8:5
Queue: 1:9:2, 3:9:4, 6:14:4
Visit 1:9:2
Find: 3:18
Visited: 1:9:2, 2:2:5, 4:6:5, 5:-1:-1, 7:8:5
Queue: 3:9:4, 6:14:4
Visit 3:9:4
Find: 6:13
Visited: 1:9:2, 2:2:5, 3:9:4, 4:6:5, 5:-1:-1, 7:8:5
Queue: 6:13:3
Visit to 6:13:3 finds nothing
Final: 1:9:2, 2:2:5, 3:9:4, 4:6:5, 5:-1:-1, 6:13:3, 7:8:5
7
5
10
1 2 7
1 3 9
2 4 15
2 5 2
3 4 3
3 6 4
4 5 6
4 6 8
5 7 8
6 7 16
7
1 9 2
2 2 5
3 9 4
4 6 5
5 -1 -1
6 13 3
7 8 5
Dijkstra’s Algorithm
COP3503 COMPUTER SCIENCE II
DR. MATTHEW B. GERBER
PORTIONS FROM SEAN SZUMLANSKI, MICHAEL MCALPIN,
WIKIPEDIA, AND WOLFRAM MATHWORLD
Minimum Spanning Tree
◦ We talked about the notion of a minimum spanning tree
◦ Finding the minimum edge cost needed to connect a graph with a minimum number of edges
◦ This has obvious applications, but there’s a related problem with even more obvious ones
Shortest Paths
◦ We talked about the notion of a minimum spanning tree
◦ Finding the minimum edge cost needed to connect a graph
◦ This has obvious applications, but there’s a related problem with even more obvious ones
◦ Shortest Paths
◦ Finding the minimum edge cost to traverse from one node to another node
◦ Obviously related to the minimum spanning tree problem…
Shortest Paths
◦ We talked about the notion of a minimum spanning tree
◦ Finding the minimum edge cost needed to connect a graph
◦ This has obvious applications, but there’s a related problem with even more obvious ones
◦ Shortest Paths
◦ Finding the minimum edge cost to traverse from one node to another node
◦ Obviously related to the minimum spanning tree problem…
◦ …but you can’t just make a minimum spanning tree and call it a day
◦ There are a lot of ways to do this…
◦ But the foundational algorithm was found in 1956
◦ And is still the foundational algorithm today
Dijkstra’s Algorithm: Initialization
◦ Mark all nodes as unvisited
1
4
2
2
3
3
7
5
9
1
5
8
4
3
6
Dijkstra’s Algorithm: Initialization
◦ Mark all nodes as unvisited
1
4
2
2
3
3
7
5
9
1
5
8
4
3
6
Dijkstra’s Algorithm: Initialization
◦ Mark all nodes as unvisited
◦ Give every node a current distance of infinity
1
∞
◦ (except our source node)
4
2
∞
2
3
∞
3
8
7
5
9
1
5
–
4
∞
3
6
∞
Dijkstra’s Algorithm: Initialization
◦ Mark all nodes as unvisited
◦ Give every node a current distance of infinity
1
∞: U
◦ (except our source node)
◦ Mark every node’s parent as undefined
4
◦ (except our source node)
2
∞: U
2
3
∞: U
3
8
7
5
9
1
5
–
4
∞: U
3
6
∞: U
Dijkstra’s Algorithm: Initialization
◦ Mark all nodes as unvisited
◦ Give every node a current distance of infinity
1
∞: U
◦ (except our source node)
◦ Mark every node’s parent as undefined
4
◦ (except our source node)
◦ Mark the source node as current
2
∞: U
2
3
∞: U
3
8
7
5
9
1
5
–
4
∞: U
3
6
∞: U
Dijkstra’s Algorithm: Iteration
While we have unvisited vertices:
◦ For each unvisited neighbor of the current vertex:
1
∞: U
4
2
∞: U
2
3
∞: U
3
8
7
5
9
1
5
–
4
∞: U
3
6
∞: U
Dijkstra’s Algorithm: Iteration
While we have unvisited vertices:
◦ For each unvisited neighbor of the current vertex:
1
∞: U
◦ Calculate the distance through the current node
◦ That’s the current distance of the current node plus the cost of
the edge to the neighbor
4
2
∞: U
2
3
∞: U
3
8
7
5
9
1
5
–
4
∞: U
3
6
∞: U
Dijkstra’s Algorithm: Iteration
While we have unvisited vertices:
◦ For each unvisited neighbor of the current vertex:
◦ Calculate the distance through the current node
◦ That’s the current distance of the current node plus the cost of
the edge to the neighbor
4
2
∞: U
2
3
∞: U
1
∞: U 3
3
8
7
5
9
1
5
–
4
∞: U
3
6
∞: U
Dijkstra’s Algorithm: Iteration
While we have unvisited vertices:
◦ For each unvisited neighbor of the current vertex:
◦ Calculate the distance through the current node
◦ That’s the current distance of the current node plus the cost of
the edge to the neighbor
4
2
∞: U 8
2
3
∞: U
1
∞: U 3
3
8
7
5
9
1
5
–
4
∞: U
3
6
∞: U
Dijkstra’s Algorithm: Iteration
While we have unvisited vertices:
◦ For each unvisited neighbor of the current vertex:
◦ Calculate the distance through the current node
◦ That’s the current distance of the current node plus the cost of
the edge to the neighbor
4
2
∞: U 8
2
3
∞: U
9
1
1
∞: U 3
3
5
–
8
7
5
4 5
∞: U
3
6
∞: U
Dijkstra’s Algorithm: Iteration
While we have unvisited vertices:
◦ For each unvisited neighbor of the current vertex:
◦ Calculate the distance through the current node
◦ That’s the current distance of the current node plus the cost of
the edge to the neighbor
4
2
∞: U 8
2
3
∞: U
9
1
1
∞: U 3
3
5
–
8
7
5
4 5
∞: U
3
7
6
∞: U
Dijkstra’s Algorithm: Iteration
While we have unvisited vertices:
◦ For each unvisited neighbor of the current vertex:
◦ Calculate the distance through the current node
◦ That’s the current distance of the current node plus the cost of
the edge to the neighbor
4
◦ If it’s less than the current distance of that neighbor…
2
8: U 8
◦ Replace the neighbor’s current distance with the newly
calculated distance
2
3
∞: U
9
1
1
3: U 3
3
5
–
8
7
5
4 5
5: U
3
7
6
7: U
Dijkstra’s Algorithm: Iteration
While we have unvisited vertices:
◦ For each unvisited neighbor of the current vertex:
1
3: 5
◦ Calculate the distance through the current node
◦ That’s the current distance of the current node plus the cost of
the edge to the neighbor
4
◦ If it’s less than the current distance of that neighbor…
2
8: 5
◦ Replace the neighbor’s current distance with the newly
calculated distance
◦ Replace the neighbor’s parent with the current node
2
3
∞: U
8
9
1
3
3
5
–
8
7
5
4 5
5: 5
3
7
6
7: 5
Dijkstra’s Algorithm: Iteration
While we have unvisited vertices:
◦ For each unvisited neighbor of the current vertex:
1
3: 5
◦ Calculate the distance through the current node
◦ That’s the current distance of the current node plus the cost of
the edge to the neighbor
4
◦ If it’s less than the current distance of that neighbor…
2
8: 5
◦ Replace the neighbor’s current distance with the newly
calculated distance
◦ Replace the neighbor’s parent with the current node
◦ Mark the current vertex visited
2
3
∞: U
8
9
1
3
3
5
–
8
7
5
4 5
5: 5
3
7
6
7: 5
Dijkstra’s Algorithm: Iteration
While we have unvisited vertices:
◦ For each unvisited neighbor of the current vertex:
1
3: 5
◦ Calculate the distance through the current node
◦ That’s the current distance of the current node plus the cost of
the edge to the neighbor
4
◦ If it’s less than the current distance of that neighbor…
2
8: 5
◦ Replace the neighbor’s current distance with the newly
calculated distance
◦ Replace the neighbor’s parent with the current node
◦ Mark the current vertex visited
◦ Set an unvisited node with a lowest current distance
current
2
3
∞: U
3
8
7
5
9
1
5
–
4
5: 5
3
6
7: 5
Dijkstra’s Algorithm: Iteration
While we have unvisited vertices:
◦ For each unvisited neighbor of the current vertex:
1
3: 5
◦ Calculate the distance through the current node
◦ That’s the current distance of the current node plus the cost of
the edge to the neighbor
4
◦ If it’s less than the current distance of that neighbor…
◦ Replace the neighbor’s parent with the current node
◦ Mark the current vertex visited
◦ Set an unvisited node with a lowest current distance
current
7
2
8: 5
◦ Replace the neighbor’s current distance with the newly
calculated distance
2
3
∞: U
3
8
7
5
9
1
5
–
4
5: 5
3
6
7: 5
Dijkstra’s Algorithm: Iteration
While we have unvisited vertices:
◦ For each unvisited neighbor of the current vertex:
1
3: 5
◦ Calculate the distance through the current node
◦ That’s the current distance of the current node plus the cost of
the edge to the neighbor
4
◦ If it’s less than the current distance of that neighbor…
◦ Replace the neighbor’s parent with the current node
◦ Mark the current vertex visited
◦ Set an unvisited node with a lowest current distance
current
7
2
7: 1
◦ Replace the neighbor’s current distance with the newly
calculated distance
2
3
∞: U
3
8
7
5
9
1
5
–
4
5: 5
3
6
7: 5
Dijkstra’s Algorithm: Iteration
While we have unvisited vertices:
◦ For each unvisited neighbor of the current vertex:
1
3: 5
◦ Calculate the distance through the current node
◦ That’s the current distance of the current node plus the cost of
the edge to the neighbor
4
◦ If it’s less than the current distance of that neighbor…
2
7: 1
◦ Replace the neighbor’s current distance with the newly
calculated distance
◦ Replace the neighbor’s parent with the current node
◦ Mark the current vertex visited
◦ Set an unvisited node with a lowest current distance
current
2
3
∞: U
3
8
7
5
9
1
5
–
4
5: 5
3
6
7: 5
Dijkstra’s Algorithm: Iteration
While we have unvisited vertices:
◦ For each unvisited neighbor of the current vertex:
1
3: 5
◦ Calculate the distance through the current node
◦ That’s the current distance of the current node plus the cost of
the edge to the neighbor
4
◦ If it’s less than the current distance of that neighbor…
2
7: 1
◦ Replace the neighbor’s current distance with the newly
calculated distance
◦ Replace the neighbor’s parent with the current node
◦ Mark the current vertex visited
◦ Set an unvisited node with a lowest current distance
current
2
3
∞: U
6
3
14
8
7
5
9
1
5
–
4
5: 5
3
13
6
7: 5
Dijkstra’s Algorithm: Iteration
While we have unvisited vertices:
◦ For each unvisited neighbor of the current vertex:
1
3: 5
◦ Calculate the distance through the current node
◦ That’s the current distance of the current node plus the cost of
the edge to the neighbor
4
◦ If it’s less than the current distance of that neighbor…
2
7: 1
◦ Replace the neighbor’s current distance with the newly
calculated distance
◦ Replace the neighbor’s parent with the current node
◦ Mark the current vertex visited
◦ Set an unvisited node with a lowest current distance
current
2
3
6: 4
6
3
14
8
7
5
9
1
5
–
4
5: 5
3
13
6
7: 5
Dijkstra’s Algorithm: Iteration
While we have unvisited vertices:
◦ For each unvisited neighbor of the current vertex:
1
3: 5
◦ Calculate the distance through the current node
◦ That’s the current distance of the current node plus the cost of
the edge to the neighbor
4
◦ If it’s less than the current distance of that neighbor…
2
7: 1
◦ Replace the neighbor’s current distance with the newly
calculated distance
◦ Replace the neighbor’s parent with the current node
◦ Mark the current vertex visited
◦ Set an unvisited node with a lowest current distance
current
2
3
6: 4
3
8
7
5
9
1
5
–
4
5: 5
3
6
7: 5
Dijkstra’s Algorithm: Iteration
While we have unvisited vertices:
◦ For each unvisited neighbor of the current vertex:
1
3: 5
◦ Calculate the distance through the current node
◦ That’s the current distance of the current node plus the cost of
the edge to the neighbor
4
◦ If it’s less than the current distance of that neighbor…
◦ Replace the neighbor’s current distance with the newly
calculated distance
8
◦ Replace the neighbor’s parent with the current node
◦ Mark the current vertex visited
◦ Set an unvisited node with a lowest current distance
current
2
7: 1
2
3
6: 4
3
8
7
5
9
1
5
–
4
5: 5
3
6
7: 5
Dijkstra’s Algorithm: Iteration
While we have unvisited vertices:
◦ For each unvisited neighbor of the current vertex:
1
3: 5
◦ Calculate the distance through the current node
◦ That’s the current distance of the current node plus the cost of
the edge to the neighbor
4
◦ If it’s less than the current distance of that neighbor…
◦ Replace the neighbor’s current distance with the newly
calculated distance
8
◦ Replace the neighbor’s parent with the current node
◦ Mark the current vertex visited
◦ Set an unvisited node with a lowest current distance
current
2
7: 1
2
3
6: 4
3
8
7
5
9
1
5
–
4
5: 5
3
6
7: 5
Dijkstra’s Algorithm: Iteration
While we have unvisited vertices:
◦ For each unvisited neighbor of the current vertex:
1
3: 5
◦ Calculate the distance through the current node
◦ That’s the current distance of the current node plus the cost of
the edge to the neighbor
4
◦ If it’s less than the current distance of that neighbor…
2
7: 1
◦ Replace the neighbor’s current distance with the newly
calculated distance
◦ Replace the neighbor’s parent with the current node
◦ Mark the current vertex visited
◦ Set an unvisited node with a lowest current distance
current
2
3
6: 4
3
8
7
5
9
1
5
–
4
5: 5
3
6
7: 5
Dijkstra’s Algorithm: Iteration
While we have unvisited vertices:
◦ For each unvisited neighbor of the current vertex:
1
3: 5
◦ Calculate the distance through the current node
◦ That’s the current distance of the current node plus the cost of
the edge to the neighbor
4
◦ If it’s less than the current distance of that neighbor…
2
7: 1
◦ Replace the neighbor’s current distance with the newly
calculated distance
◦ Replace the neighbor’s parent with the current node
◦ Mark the current vertex visited
◦ Set an unvisited node with a lowest current distance
current
2
3
6: 4
3
8
7
5
9
1
5
–
4
5: 5
3
6
7: 5
Dijkstra’s Algorithm: Iteration
While we have unvisited vertices:
◦ For each unvisited neighbor of the current vertex:
1
3: 5
◦ Calculate the distance through the current node
◦ That’s the current distance of the current node plus the cost of
the edge to the neighbor
4
◦ If it’s less than the current distance of that neighbor…
2
7: 1
◦ Replace the neighbor’s current distance with the newly
calculated distance
◦ Replace the neighbor’s parent with the current node
◦ Mark the current vertex visited
◦ Set an unvisited node with a lowest current distance
current
2
3
6: 4
3
8
7
5
9
1
5
–
4
5: 5
3
6
7: 5
Dijkstra’s Algorithm: Cleanup
We now can read the path from each vertex
backwards…
1
3: 5
4
2
7: 1
2
3
6: 4
3
8
7
5
9
1
5
–
4
5: 5
3
6
7: 5
Dijkstra’s Algorithm: Cleanup
We now can read the path from each vertex
backwards…
1
3: 5
4
2
7: 1
2
3
6: 4
3
8
7
5
9
1
5
–
4
5: 5
3
6
7: 5
Dijkstra’s Algorithm: Cleanup
We now can read the path from each vertex
backwards…
1
3: 5
4
2
7: 1
2
3
6: 4
3
8
7
5
9
1
5
–
4
5: 5
3
6
7: 5
Dijkstra’s Algorithm: Cleanup
We now can read the path from each vertex
backwards…
1
3: 5
4
2
7: 1
2
3
6: 4
3
8
7
5
9
1
5
–
4
5: 5
3
6
7: 5
Dijkstra’s Algorithm: Cleanup
We now can read the path from each vertex
backwards…
1
3: 5
4
2
7: 1
2
3
6: 4
3
8
7
5
9
1
5
–
4
5: 5
3
6
7: 5
Dijkstra’s Algorithm: Cleanup
We now can read the path from each vertex
backwards…
1
3: 5
4
2
7: 1
2
3
6: 4
3
8
7
5
9
1
5
–
4
5: 5
3
6
7: 5
Dijkstra’s Algorithm: Cleanup
We now can read the path from each vertex
backwards…
1
3: 5
◦ That’s a spanning tree!
4
2
7: 1
2
3
6: 4
3
8
7
5
9
1
5
–
4
5: 5
3
6
7: 5
Dijkstra’s Algorithm: Cleanup
We now can read the path from each vertex
backwards…
1
3: 5
◦ That’s a spanning tree!
◦ We now have a shortest path from all vertices to
vertex 5, and vice versa
4
2
7: 1
2
3
6: 4
3
8
7
5
9
1
5
–
4
5: 5
3
6
7: 5
Dijkstra’s Algorithm: Cleanup
We now can read the path from each vertex
backwards…
1
3: 5
◦ That’s a spanning tree!
◦ We now have a shortest path from all vertices to
vertex 5, and vice versa
4
2
7: 1
If we just want the path to one other destination
vertex, we can just stop once we mark the
destination vertex visited
◦ (In fact, we can stop a bit before that – once the
destination vertex is a candidate for becoming current)
2
3
6: 4
3
8
7
5
9
1
5
–
4
5: 5
3
6
7: 5
Bellman-Ford Algorithm
◦ The Bellman-Ford Algorithm is similar to
Dijkstra’s, but lacks Dijkstra’s effectively greedy
characteristics
◦ It simply re-computes all weights ( 𝑉 − 1)
times – the maximum length of an acyclic path
◦ This is slower than Dijkstra’s algorithm – but can
handle negative numbers, which Dijkstra’s
algorithm cannot
◦ It breaks if there’s a cycle with a negative
weight…
◦ Mark all nodes as unvisited
◦ Give every node a current distance of infinity
◦ (except our source node)
◦ Mark every node’s parent as undefined
◦ (except our source node)
◦ Repeat 𝑉 − 1 times:
◦ For each edge 𝑒 = (𝑢, 𝑣):
◦ Let 𝑤 = 𝑒. 𝑤𝑒𝑖𝑔ℎ𝑡
◦ If 𝑢. 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 + 𝑤 < 𝑣. 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒
◦ Let 𝑣. 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 = 𝑢. 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 + 𝑤
◦ 𝑣. 𝑝𝑎𝑟𝑒𝑛𝑡 = 𝑢
Bellman-Ford Algorithm
◦ The Bellman-Ford Algorithm is similar to
Dijkstra’s, but lacks Dijkstra’s effectively greedy
characteristics
◦ It simply re-computes all weights ( 𝑉 − 1)
times – the maximum length of an acyclic path
◦ This is slower than Dijkstra’s algorithm – but can
handle negative numbers, which Dijkstra’s
algorithm cannot
◦ It breaks if there’s a cycle with a negative
weight…
◦ …but it can also detect those!
◦ Mark all nodes as unvisited
◦ Give every node a current distance of infinity
◦ (except our source node)
◦ Mark every node’s parent as undefined
◦ (except our source node)
◦ Repeat 𝑉 − 1 times:
◦ For each edge 𝑒 = (𝑢, 𝑣):
◦ Let 𝑤 = 𝑒. 𝑤𝑒𝑖𝑔ℎ𝑡
◦ If 𝑢. 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 + 𝑤 < 𝑣. 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒
◦ Let 𝑣. 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 = 𝑢. 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 + 𝑤
◦ 𝑣. 𝑝𝑎𝑟𝑒𝑛𝑡 = 𝑢
◦ For each edge 𝑒 = (𝑢, 𝑣):
◦ Let 𝑤 = 𝑒. 𝑤𝑒𝑖𝑔ℎ𝑡
◦ If 𝑢. 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 + 𝑤 < 𝑣. 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒
◦ Throw exception: Negative-weight cycle
