Fandom

Math Wiki

Dijkstra's algorithm

1,016pages on
this wiki
Add New Page
Talk0 Share

Dijkstra's algorithm is one of the most widely used methods for finding single-source shortest paths in a simple digraph. In other words, Dijkstra's algorithm determines the shortest paths from a common vertex s to all other vertices in a digraph, if they exist.

Algorithm

Let G = (V,A) be a simple digraph with a function w(a) : A \to {\mathbb{R}}^{+} which assigns a weight, a non-negative real number, to each arc in G. Fix a source vertex s in G, from which shortest paths will be found.

Additionally, for the purposes of the search itself, let d(v) denote the length of the shortest path from s to v. Let S denote the set of visited vertices, i.e., those vertices that have already been examined by the algorithm. Given a path \pi in G determined by the algorithm, let p(v) denote the predecessor of v for any v in \pi such that v \ne s. The meanings of these additions will become clear in the description of the algorithm. The execution proceeds as follows.

Initial Stage

  1. Let d(s) = 0. [1]
  2. For each vertex v adjacent from s, let d(v) be w((s,v)), and let p(v) = s.
  3. For each vertex v such that v \ne s and v is not adjacent from s, let d(v) = \infty. [2]
  4. Let S = \{s\}. [3]

Iterative Stage

  1. Determine the vertex v that minimizes d(v) in V \setminus S, i.e., an unvisited vertex.
  2. For each vertex u adjacent from v, compare the current value d(u) and n = d(v) + w((v,u)). If n is the least of the two, let d(u) = n, and let p(u) = v.
  3. Mark v as visited. That is, let S = S \cup \{v\}.
  4. If S = V, all vertices have been visited; halt. Otherwise, return to the first step.

Additional Details

Interpretation of Results

When the execution terminates, every vertex v for which d(v) < \infty has a shortest path. This shortest path is determined by repeated application of p(v) to v. For instance, a shortest path from s to v, four vertices long, would be described (s,p(p(v)),p(v),v). For any vertex v where d(v) = \infty, there is, of course, no shortest path from s to v.

Non-negativity Constraint

Because Dijkstra's algorithm is a special case of uniform cost search, where there is no particular goal state, it is essential that w(a) \ge 0 for all arcs in G.

Dynamic Programming

Dijkstra's algorithm is also an instance of dynamic programming.[4] Let S_i equal the value of S in the ith iteration of the algorithm, where i=0 initially and S_0 = \{s\}. Let d(v,S_i) denote the weight of the shortest path from s to v, given the knowledge of S_i. Then

Failed to parse (lexing error): w(v,S_i) = \begin{cases} 0 & \text{for $v = s$} \\ \min\{w((u,v)) + d(u, S_i)\} & \text{for $v \neq s$, where $v$ is adjacent from $u \in S_i$} \\ \infty & \text{otherwise} \end{cases}


Therefore, the purpose of Dijkstra's algorithm is to determine the best policy for transforming the state of the problem (i.e., which vertex to move to next). It does so by refining an approximation of the best shortest-path policy for all vertices with each iteration, until the full solution is realized. The algorithm is efficient in practice because each iteration relies on previously determined information.

Notes

  1. ...since there is no effort in staying in place.
  2. That is, the distance is unknown and v is assumed to be unreachable until it is proven otherwise.
  3. ...since no paths from s to itself need to be considered.
  4. To preempt any accusations of plagiarism, the description that follows was cribbed by the author from an article he himself wrote on PlanetMath.

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.