Yao Lirong's Blog

Shortest path algorithm

CS2112
2019/11/21

From Lecture: Dijkstra’s shortest path algorithm

Dijkstra

  • white: dist == infinity
  • gray: dist < infinity, in queue
  • black: dist < infinity, not in queue
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
root.dist = 0; //root is the source
frontier.push(root); //root is now grey
while(!frontier.empty()){
    Node g = frontier.pop();
    for (g -> v){
        if(v.dist==infinity){ //found a new white node
            v.dist = g.dist + d;
            frontier.push(v);
        }
        else{ // v is grey
            v.dist = min(v.dist, g.dist+d);
        }
    }
    //g is now black
}

v1 and v2 is on the best path iff v1.dist+d=v2.dist

Therefore, if we want to get the shortest path, we can use this algorithm to walk straight back to the graph from destination.

Performance

Total: O((V+E)lgV)

  • outer loop: O(V lgV)
    • once per vertex, O(V) iterations
    • finding min element in the queue once: O(lg V) - BST or heap
  • inneer loop: O(E lgV)
    • O(E) iterations
    • time to push/update priority queue: O(lg V)

Correctness

Loop Invariant:

  1. For every black node b, gray g: b.dist<=g.dist
  2. v.dist is length of shortest interior path to v (or infinity if none) (interior path means it stays in the black region, which means it only uses black nodes)

Establishment:

no black nodes

PostCondition:

  1. no gray nodes
  2. all the nodes are black -> All paths are interior path -> shortest: interior path is actual answer

Preservation:

不写了，👴 后面看不懂了。

Application:

if you have something like condition probability which has to be multiplied to produce the correct result. But so you want to know the shortest probability there. You can just take the log of probability.

For example, suppose that we had a state machine that transitioned to new states with some given probability on each outgoing edge. The probability of taking a particular path through the graph would then be the product of the probabilities on edges along that path. We can then answer questions such as, “What is the most likely path that the system will follow in order to arrive at a given state?” by solving a shortest path problem in a weighted graph in which the weights are the negative logarithms of the probabilities, since $(−log a) + (−log b) = −log ab$.

Author：Yao Lirong

Link：https://yao-lirong.github.io/blog/2019-11-21-shortest-path-algorithm/

Publish date：November 21st 2019, 12:00:00 am

Update date：June 9th 2022, 3:14:34 am

License：本文采用 Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0) 进行许可

CATALOG
  1. 1. Dijkstra
    1. 1.1. Performance
    2. 1.2. Correctness
      1. 1.2.1. Loop Invariant:
      2. 1.2.2. Establishment:
      3. 1.2.3. PostCondition:
      4. 1.2.4. Preservation:
  2. 2. Application:
Total : 66
2023
2022
2021
2020
2019
NOI CS2112 Logistics Cornell Review CS3110 Manual Journal Tsinghua Book