|
|
|
|
-> Set the distance from the source to source to 0 -> Set the distance from all nodes (except from source) to the source to a very large value (infinite) -> Put all nodes in the graph into the min priority queue -> prev_node is null -> while the priority queue is not empty: ----> remove the node u with the smallest priority from the queue ----> set prev_node as the previous node to this node ----> prev_node is u ----> for all nodes v having an edge to this node: -------> if distance to u plus distance from u to v is smaller than current distance stored at v -----------> update v's distance -----------> and set v's previous node as prev_node -----------> reorder v in the priority queue |
|
|
34 34 34 34 34 35 36 -1 32 32 32 32 33 34 35 36 37 38 39 40 -1 22 21 20 19 18 17 16 16 16 16 33 33 33 33 34 35 36 -1 31 31 31 32 33 34 35 36 37 38 39 40 -1 22 21 20 19 18 17 16 15 15 15 32 32 32 33 34 35 36 -1 30 30 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 14 15 32 31 -1 -1 -1 -1 -1 -1 29 29 29 30 31 32 33 34 35 36 37 38 -1 10 10 11 12 13 13 13 13 14 15 32 31 30 29 28 28 28 28 28 28 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 9 -1 11 12 12 12 12 13 14 15 32 31 30 29 28 27 27 27 27 27 -1 4 3 2 1 0 1 2 3 4 -1 8 -1 11 11 11 11 12 13 14 15 32 31 30 29 28 27 26 26 26 26 -1 4 3 2 1 1 1 2 3 4 -1 7 -1 10 10 10 11 12 13 14 15 32 31 30 29 28 27 26 25 25 25 -1 4 3 2 2 2 2 2 3 4 -1 6 -1 9 9 10 11 12 13 14 15 32 31 30 29 28 27 26 25 24 24 -1 4 3 3 3 3 3 3 3 4 5 6 -1 8 9 10 11 12 13 14 15 32 31 30 29 28 27 26 25 24 23 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 6 7 8 9 10 11 12 13 14 15 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 17 17 17 17 -1 7 7 8 9 10 11 12 13 14 15 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 16 16 16 -1 8 8 8 9 10 11 12 13 14 15 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 15 15 -1 9 9 9 9 10 11 12 13 14 15 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 14 -1 10 10 10 10 10 11 12 13 14 15 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 -1 11 11 11 11 11 11 12 13 14 15 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 -1 -1 12 12 12 12 12 12 12 12 13 14 15 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 16 -1 13 13 13 13 13 13 13 13 13 13 14 15 |
|
|