[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / wiki/concepts/dijikstra_s_algorithm.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "Dijikstra's Algorithm" type: concept related: [Graph, Red Black Tree] source: https://www.jemoka.com/posts/kbhdijikstra_s_algorithm/ confidence: high status: active --- 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 pick the node \(u\) that has unlabeled state with smallest \(d\qty(u)\) for all neighbor v of u: set \(d\qty(v) = \min \qty(d\qty(v), d\qty(u) + \text{edgeWeight}\qty(u,v))\) mark \(v\) as labeled def dike(G,s,t): set verticies to State.NOTSURE for v in G.V: d[v] = float("+inf") p[v] = None # (for parents) d[s] = 0 while State.NOTSURE in G.V: # get node with minimum distance that's not sure u = argmin(d[v] for v in G.V if v.state == State.NOTSURE) u.state = State.SURE for v in u.out_neighbors: d[v] = min(d[v], d[u] + edgeWeight(u,v)) if d[v] was changed: p[v] = u # (for obtaining next path in chain for shortes paths) 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: store unsure verticies \(v\) keep track of \(d[v]\) find the minimum vertex \(d[u]\) can update \(d[u]\) 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))\) In a Fib Heap: \(O\qty(n \log n + m)\).