❑ Dijkstra algorithm : An algorithm to find the shortest path between two nodes.
❑ Example : Find the shortest path based on node [0].
[Initial state]
[Step 1]
S = {0}
D[] = [0, 7, 999, 999, 3, 10, 999]
* Visit the first node [0].
* The distance from node [0] to node [4], [1], [5] can be checked and It is reflected in D[].
[Step 2]
S = {0, 4}
D[] = [0, 5, 999, 14, 3, 10, 8]
* Visit the nearest node [4]([0]→[4]).
* The distances to adjacent nodes when visiting node [4] are reflected in D[].
[Step 3]
S = {0, 4, 1}
D[] = [0, 5, 9, 14, 3, 10, 8]
* Visit the nearest node [1]([0]→[4]→[1]).
[Step 4]
S = {0, 4, 1, 6}
D[] = [0, 5, 9, 12, 3, 10, 8]
* Visit the nearest node [6] that is not visited([0]→[4]→[6]).
[Step 5]
S = {0, 4, 1, 6, 2}
D[] = [0, 5, 9, 11, 3, 10, 8]
* Visit the nearest node [2]([0]→[4]→[1]→[2]).
[Step 6]
S = {0, 4, 1, 6, 2, 3}
D[] = [0, 5, 9, 11, 3, 10, 8]
* Visit the nearest node [3]([0]→[4]→[1]→[2]→[3]).
* Even if node [3] is visited, but D[] is not changed..
* The algorithm terminates when all nodes are visited.
※ The total identified shortest paths.
1. [0]
2. [0]→[4]
3. [0]→[4]→[6]
4. [0]→[4]→[1]
5. [0]→[4]→[1]→[2]
6. [0]→[4]→[1]→[2]→[3]
7. [0]→[5]