Dijkstra's ALGORITHM
STUDENT'S NIGHT OUT PROBLEM
Step 1:
To illustrate Dijkstra’s algorithm, we will find the shortest path from node 1 (Engineering Building) to node 14 (Springbok’s Pub).
We begin with the following labels; where a * represents a permanent label, and the ith number is the distance to the node i (i = 1;2;3;…;14).
[0* 1200 1400 1100 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞]
[node1 node2 node3 node4 … node14 ]
We label node 1 with a permanent label 0*.
Then we label each node i that is connected to node 1 by a single arc with a “temporary” label equal to the length of the arc joining node 1 and node i.
As there is no direct paths (nodes connected by a single arc) between node 1 and node 4;…;14 these distances are represented by ∞
Step 2:
Node 4 has the smallest temporary label.
We therefore make node 4’s label permanent and obtain the following labels:
[0* 1200 1400 1100* ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞]
We now know that node 4 is the closest node to node 1.
We next compute temporary labels for all nodes that are connected to node 4 by a single arc.
We begin with the following labels; where a * represents a permanent label, and the ith number is the distance to the node i (i = 1;2;3;…;14).
[0* 1200 1400 1100 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞]
[node1 node2 node3 node4 … node14 ]
We label node 1 with a permanent label 0*.
Then we label each node i that is connected to node 1 by a single arc with a “temporary” label equal to the length of the arc joining node 1 and node i.
As there is no direct paths (nodes connected by a single arc) between node 1 and node 4;…;14 these distances are represented by ∞
Step 2:
Node 4 has the smallest temporary label.
We therefore make node 4’s label permanent and obtain the following labels:
[0* 1200 1400 1100* ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞]
We now know that node 4 is the closest node to node 1.
We next compute temporary labels for all nodes that are connected to node 4 by a single arc.
Node: Temporary Label
Node 5 min{∞; 1100 + 50} = 1150*
Node 7 min{∞; 1100 + 950} = 2050
Node 8 min{∞; 1100 + 350} = 1450
Node 5 min{∞; 1100 + 50} = 1150*
Node 7 min{∞; 1100 + 950} = 2050
Node 8 min{∞; 1100 + 350} = 1450
We obtain the following labels:
[0* 1100* 1150 ∞ 2050 1450 ∞ ∞ ∞ ∞ ∞ ∞]
Step 3:
Node 5 has the smallest temporary label.
We therefore make node 5’s label permanent and obtain the following labels:
[0* 1100* 1150* ∞ 2050 1450 ∞ ∞ ∞ ∞ ∞ ∞]
We now know that node 5 is the second closest node to node 1.
We next compute temporary labels for all nodes that are connected to node 5 by a single arc.
[0* 1100* 1150 ∞ 2050 1450 ∞ ∞ ∞ ∞ ∞ ∞]
Step 3:
Node 5 has the smallest temporary label.
We therefore make node 5’s label permanent and obtain the following labels:
[0* 1100* 1150* ∞ 2050 1450 ∞ ∞ ∞ ∞ ∞ ∞]
We now know that node 5 is the second closest node to node 1.
We next compute temporary labels for all nodes that are connected to node 5 by a single arc.
Node: Temporary Label
Node 9 min{∞; 1150 + 240} = 1390*
Node 9 min{∞; 1150 + 240} = 1390*
We obtain the following labels:
[0* 1100* 1150* 1390* ∞ ∞ ∞ ∞ ∞]
Step 4:
Node 9 has the only temporary label as it’s the only node with a direct path from node 5.
We therefore make node 9’s label permanent and obtain the following labels:
[0* 1100* 1150* 1390* ∞ ∞ ∞ ∞ ∞]
We next compute temporary labels for all nodes that are connected to node 9 by a single arc.
[0* 1100* 1150* 1390* ∞ ∞ ∞ ∞ ∞]
Step 4:
Node 9 has the only temporary label as it’s the only node with a direct path from node 5.
We therefore make node 9’s label permanent and obtain the following labels:
[0* 1100* 1150* 1390* ∞ ∞ ∞ ∞ ∞]
We next compute temporary labels for all nodes that are connected to node 9 by a single arc.
Node: Temporary Label
Node 11 min{∞; 1390 + 500} = 1890
Node 12 min{∞; 1390 + 350} = 1740
Node 13 min{∞; 1390 + 130} = 1520*
Node 11 min{∞; 1390 + 500} = 1890
Node 12 min{∞; 1390 + 350} = 1740
Node 13 min{∞; 1390 + 130} = 1520*
We obtain the following labels:
[0* 1100* 1150* 1390* ∞ 1890 1740 1520 ∞]
Step 5:
Node 13 has the smallest temporary label.
We therefore make node 13’s label permanent and obtain the following labels:
[0* 1100* 1150* 1390* ∞ 1890 1740 1520* ∞]
We now only have one node left.
We compute temporary labels for the node that connects the last node, node 14, by a single arc.
[0* 1100* 1150* 1390* ∞ 1890 1740 1520 ∞]
Step 5:
Node 13 has the smallest temporary label.
We therefore make node 13’s label permanent and obtain the following labels:
[0* 1100* 1150* 1390* ∞ 1890 1740 1520* ∞]
We now only have one node left.
We compute temporary labels for the node that connects the last node, node 14, by a single arc.
Node: Temporary Label
Node 14 min{∞; 1520 + 390} = 1910*
Node 14 min{∞; 1520 + 390} = 1910*
Conclusion:
We obtain the following labels:
[0* 1100* 1150* 1390* 1520* 1910]
Our final set of labels is:
[0* 1100* 1150* 1390* 1520* 1910*]
We can now work backwards and find the shortest path from node 1 to node 14. The permanent label for node 14 represents the length of the shortest path, thus 1910m. The difference between the permanent labels of the nodes represents the lengths of the arc (path) between the nodes.
[0* 1100* 1150* 1390* 1520* 1910]
Our final set of labels is:
[0* 1100* 1150* 1390* 1520* 1910*]
We can now work backwards and find the shortest path from node 1 to node 14. The permanent label for node 14 represents the length of the shortest path, thus 1910m. The difference between the permanent labels of the nodes represents the lengths of the arc (path) between the nodes.
E.g. Node 13 – Node 9
1520 – 1390 = 130
1520 – 1390 = 130
Our final labels thus represents the following path through the nodes as the shortest path:
[Node1 Node4 Node5 Node9 Node13 Node14]
with a total path length of 1910m.
[Node1 Node4 Node5 Node9 Node13 Node14]
with a total path length of 1910m.
dijkstras_algorithm.pptx | |
File Size: | 53 kb |
File Type: | pptx |