Dijkstra’s
shortest path algorithm
•Algorithm
1.init node costs to ¥, set p = seed point, cost(p) = 0
2.expand p as follows:
for each of p’s neighbors q that are
not expanded
–set cost(q) = min( cost(p) + cpq, cost(q) )
»if q’s cost changed, make q point back to p
–put q on the ACTIVE list (if not already there)
3.set r = node with minimum
cost on the ACTIVE list
4.repeat Step 2 for p = r
3
1
0
5
3
3
2
3
6
5
3
1
3
3
4
9
2
4
3
1
4
5
2
3
3
3
2
4
2