Dijikstra's Algorithm

constituents

  • a weighted directed graph, meaning edges have weights
  • where cost of a path is the sum of the weights along that path
  • the shortest path is the path with the minimum cost
  • starting node \(s\), target node \(t\)

Each node has two states:

  • unlabeled
  • labeled

And stores a piece of information:

\(d\qty(v) = \text{distance}\qty(s, v)\)

We initialize \(d\qty(v) = \infty, v \neq s\) , and \(d\qty(s) = 0\).

requirements

  1. pick the node \(u\) that has unlabeled state with smallest \(d\qty(u)\)
  2. for all neighbor v of u:
    1. set \(d\qty(v) = \min \qty(d\qty(v), d\qty(u) + \text{edgeWeight}\qty(u,v))\)
  3. mark \(v\) as labeled
def dike(G,s,t):
    set verticies to State.NOTSURE
    for v in G.V:
        d[v] = float("+inf")
    d[s] = 0
    while State.NOTSURE in G.V:
        u = min(V for v in G.V if v.state == State.NOTSURE)
        for v in u.neighbors and v.state != SURE:
            d[v] = min(d[v], d[u] + edgeWeight(u,v))
        u.state = State.SURE
    return d[t]

additional information

proof

Let’s start with a lemma

Suppose \(s \to x \to t\) is the shortest path; then the sub-path \(s \to x\) is also the shortest path connecting the two.

This is true because suppose for contradiction there’s a shorter path \(s \to^{*} x\), then \(s \to^{*} x \to t\) would be a shorter path than \(s \to x \to t\), so the path \(s \to x \to t\) cannot be the shortest path between \(s \to t\) reaching contradiction.

Now, the actual theorem. Two claims sets up our proof.

for all \(v\), invariant, \(d[v] \geq d\qty(s,v)\), that all states of \(d\) is an upper bound

Recall at each step

\(d\qty(v) = \min \qty(d\qty(v), d\qty(u) + \text{edgeWeight}\qty(u,v))\)

Idea: Every time we update \(d[v]\), we either don’t change \(d[v]\) or set it to the length of a shorter path coming from \(u\). Hence, we simply continuously lowering the upper bound, and we can only get as short as the shortest path (since there are no paths lower than the shorted path.

when \(v\)’s state is done, \(d[v] = d\qty(s,v)\)

IH when we mark the \(t\) th vertex as sure, then \(d[v] = \text{dist}\qty(s,v)\).

Base case first vertex marked sure is \(s\), and we write \(d\qty(s) = d\qty(s,s) = 0\), this is indeed correct.

Inductive step

Assume by induction that every \(v\) already marked sure has \(d\qty(v) = d\qty(s,v)\).

Suppose we are about to add \(u\) to the “sure” list (meaning we are looping around its neighbors, etc.); this implies that \(u\) is an “unsure” vertex with smallest \(d[u]\). We desire that \(d[u] = \text{dist}\qty(s,u)\).

By contradiction suppose \(u\)’s distance is not correct, that \(d[u] > \text{dist}\qty(s,u)\).

(proof idea: consider shortest path \(s \to u\) to have \(s \to^{*} z \to z’ \to^{*} u\); then since subpaths of shortest path are shortest path, we know that \(s \to z\) is as shortest path, \(s \to z’\) is the shortest path, and so \(z \to z’\) forms the distance of the shortest path. If z was the last correctly labeled node, we can show that z’ was also correctly labeled, reaching contradiction).

That implies that there is some node \(z \neq u\) which is the last “correct” vertex along the shortest path. Let \(z’\) be a vertex in the shortest path, after \(z\). So, this implies that \(d[z] = \text{dist}\qty(s,z) \leq \text{dist}\qty(s,u) < d[u]\). The first inequality is true because of the lemma above, that subpath of shortest paths are shortest path. Second equality by our contradiction that \(d[u]\)’s values is not correct.

Recall than when we visited \(u\), that means that \(u\) is the smallest unsure vertex; that means that \(d[z]\) is sure. Consider the first incorrect node (i.e. for which d is wrong) in the shortest path between \(s \to z \to z’ \to u\), call this node \(z’\). We know that \(d[z’] \leq d[z] + w\qty(z, z’)\) (this is just the update in in Dike’s.) By i.h, we have \(d[z’] \leq \text{dist}\qty(s,z) + w\qty(z, z’)\) since we marked \(d[z]\) as sure. Again since subpaths of shortest paths are shortest paths, we have \(d[z’] \leq \text{dist}\qty(s,z) + w\qty(z, z’) = \text{dist}\qty(s,z’)\) and since \(d[z’]\) is always an overestimate by the lema bavoe, we have: \(d[z’] \leq \text{dist}\qty(s,z) + w\qty(z, z’) = \text{dist}\qty(s,z’) \leq d[z’]\) so \(d[z’] = \text{dist}\qty(s,z’)\). So z’ is correctly labeled, and hence we have contradiction.

Let \(G\) be a directed graph with non-negative weights; let’s run dike’s starting from \(s\). At the end of the algorithm, \(d[v]\) is the actual minimum distance \(d\qty(s,v)\).

By lemma 2, and we mark everything done eventually.

runtime

Components:

  1. store unsure verticies \(v\)
  2. keep track of \(d[v]\)
  3. find the minimum vertex \(d[u]\)
  4. can update \(d[u]\)
  5. can ignore \(u\) in find minimum (once done)

Running time:

\begin{equation} O\qty(n\qty(T\qty(\text{findMin}) + T\qty(\text{removeMin})) + m T\qty(\text{updateKey})) \end{equation}

In an array, findMin and removeMin both take \(O\qty(n)\), so this whole thing \(O\qty(n^{2})\).

In a RBT, findMin and removeMin takes \(\log \qty(n)\), so this whole thing takes \(O\qty(n\log\qty(n)) + O\qty(m \log n) = O\qty(\qty(n+m) \log\qty(n))\)