Dijkstra’s Algorithm

 

1. Single-Source Shortest Paths Problem:

    Input: Directed graph G=(V, E). (m=|E|, n=|V| )

              -- each edge has non negative length le

              -- source vertex s

    Output: for each v in V, compute L(v) := length of a shortest s-v path in G

 

2. BFS already compute shortest paths in linear time, if le = 1 for every edge e. If we replace each edge e by directed path of le unit length edges, that will blow up graph too much.

 

3. Dijkstra’s Algorithm :

    Initialize:

        a)  X = {s}  [vertices processed so far]

        b)  A[s] = 0 [computed shortest path distances]

        c)  B[s] = empty path [computed shortest paths for algorithm explanation]

    Main Loop:

        while XǂV:

             a) among all edges (v, w) in E with v in X and w not in X, pick the one that minimizes

                  A[v] + lvw , call it (v* , w*)

             b) add w* to X

             c) set A[w*] := A[v*] + lv*w*

             d) set B[w*] := B[v*] U (v*, w*)

 

4. We cannot reduce computing shortest paths with negative edge lengths to the same problem with non negative lengths by adding large constant to edge lengths. Because paths with more edges will be added more constants which don't preserve shortest paths.

 

5. Correctness Proof :

    Claim: For every directed graph with nonnegative edge lengths, Dijkstra’s algorithm correctly computes all shortestpath distances. Let A[v] be the shortest distance calculated by Dijkstra's algorithm and L[v] be the true shortest distance from s to v.

    Proof by Induction on the number of iterations:

        Base Case: A[s] = L[s] = 0.

        Inductive Hypothesis: all previous iterations are correct (i.e., A[v] = L(v) and B[v] is a true shortest s-v path in G, for all v already in X).

        In current iteration: Pick an edge (v*, w*) and we add w* to X. We set B[w*] = B[v*] u(v*, w*) , A[w*] = A[v*] + lv*w* = L(v*) + lv*w*.  Let P= any s->w* path. It must “cross the frontier” of X and V-X. 

        Let y and z be the vertices on the frontier of the path, while y is in X and z isn't. 

        Length of P = length of s-y + lyz + length of z-w* >= L[y] + lyz >= A[v*] + lv*w*

 

6. Using heap to implement Dijkstra’s Algorithm:

    Two Invariants : 

        a)  elements in heap = vertices of V-X.

        b)  for v in heap , Key[v] = smallest Dijstra greedy score of edge (u, v) in E with u in X

    By invariants, Extract-Min yields correct vertex w* to add to X and A[w*] = Key[w*].

    To maintain Invariant b) :

        When w* extracted from heap, for each edge (w*,v) in E:

           if v in V-X :

              - delete v from heap

              - recompute key[v] = min{key[v] , A[w*] + lw*v }

              - re-Insert v into heap

 

7. Running Time Analysis:

    Heap operations:

    - (n-1) Extract mins

    - each edge (v,w) triggers at most one Delete/Insert combo (if v added to X first)

    So: # of heap operations in O(n+m) = O(m)  (We assume graph is connected.)

    So: running time = O(m log(n))