The Real History of Getting Settled To Accomplish Studies

Dijkstra’s algorithm, named for its creator, the famous Dutch computer scientist Edsger W. Dijkstra, is one of the most common for finding the shortest paths from a single source vertex to other vertices in a graph that is weighted, directed and connected. Dijkstra’s is generally useful in networks where efficient traversal is very important. ¹¹In fact, this article was probably brought to you by the Shortest Path First Internet protocol, which relies on Dijkstra’s .

\theoremstyle

definition

Definition (Dijkstra’s )

Assume that $G=(V,E)$ is weighted, directed and connected. For an undirected graph, replace each edge $(v,w)$ with a pair of edges $(v,w)$ and $(w,v)$ , each having the same weight as the original undirected edge. For convenience, the weight of an edge will be denoted $d(v,w)$ , where $v$ and $w$ are its endpoints.

1.

Fix a vertex $s$ in $G$ , called the source, from which the shortest paths to all the other vertices are found.
- –
  
  Let $S$ be the set of examined vertices, initialized to $\{s\}$ .
- –
  
  Let $w(v)$ denote the of the path with minimum weight from $s$ to $v$ . For a vertex incident on an edge pointing from $s$ , $w(v)$ simply equals $d(s,v)$ . $w(s)=0$ , since it takes no effort to stay in . For all other vertices, $w(v)=\infty$ , which means that the path with minimum from $s$ to $v$ is unknown. ²²For computational purposes, this default weight was traditionally a very large number. However, IEEE 754 floating standard permits values of .
- –
  
  Let $p(v)$ denote the predecessor of $v$ , which is the previous vertex in a shortest path that can be used to back to the source. $p(v)=s$ for all vertices incident on edges pointing from $s$ .
2.

Find a vertex $v$ in $V\setminus S$ (i.e., an unexamined vertex) that minimizes $w(v)$ . If there is more than one with minimum weight, any one of them is an acceptable value of $v$ .
- –
  
  Let $S=S\cup\{v\}$ , i.e., mark $v$ as examined.
- –
  
  For each vertex $u$ such that an edge leads from $v$ to $u$ , compare the value of $w(u)$ to $w(v)+d(v,u)$ , a value that will be called $N$ .
  - *
    
    If $N$ is smaller than the value $w(u)$ , then let $w(u)=N$ and $p(u)=v$ . This incremental way of finding shorter paths is called edge relaxation.
  - *
    
    Otherwise, do nothing.
3.

Repeat previous step until $S=V$ , that is, when all vertices have been examined.

After the last iteration, for any vertex $v$ where $w(v)$ is not , the shortest path from $s$ to $v$ can be found repeated application of $p$ to $v$ until it yields $s$ . That is, the vertices in the path, in reverse , are $p(v),p(p(v)),\ldots,s$ .

Notice that there is no guarantee that this finds any shortest paths from $s$ . It simply finds whichever shortest paths do exist. In particular, when $s$ has an out-degree of zero, then all other vertices will simply be marked as examined without any changes in $w(v)$ for any value of $v$ ; there will be no shortest paths, because there are none as a rule.

Notice also that Dijkstra’s is an example of dynamic programming. Let $S_{i}$ equal the value of $S$ in the $i$ th iteration of the , where $i=0$ initially and $S_{0}$ = $\{s\}$ . Let $w(v,S_{i})$ denote the weight of the shortest path from $s$ to $v$ , given the knowledge of $S_{i}$ . Then

w(v,S_{i})=\cases{0}&\text{forv=s}\\ \min\{d(u,v)+w(u,S_{i})\}&\text{forv\neq s,wherevisadjacenttou\in S_{i}}\\ \infty&\text{otherwise}

Therefore, the purpose of Dijkstra’s 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 is realized. The is efficient in practice because each iteration relies on previously determined .

Generally speaking, the complexity of Dijkstra’s algorithm is $O(|V|^{2})$ , because in the worst-case of finding all the shortest paths from $s$ in a complete graph, $|V|-1$ comparisons are made on $|V|-1$ vertices.

[TODO: more on algorithmic complexity]

Title	The Real History of Getting Settled To Accomplish Studies
Canonical name	TheRealHistoryOfGettingSettledToAccomplishStudies
Date of creation	2013-11-27 10:59:45
Last modified on	2013-11-27 10:59:45
Owner	jacou (1000048)
Last modified by	(0)
Numerical id	26
Author	jacou (0)
Entry type	Algorithm
Classification	msc 05C85
Synonym	shortest path algorithm
Related topic	GraphTheory
Related topic	Combinatorics