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. 11In fact, this article was probably brought to you by the Shortest Path First Internet protocol, which relies on Dijkstra’s .
Definition (Dijkstra’s )
Assume that is weighted, directed and connected. For an undirected graph, replace each edge with a pair of edges and , each having the same weight as the original undirected edge. For convenience, the weight of an edge will be denoted , where and are its endpoints.
Fix a vertex in , called the source, from which the shortest paths to all the other vertices are found.
Let be the set of examined vertices, initialized to .
Let denote the of the path with minimum weight from to . For a vertex incident on an edge pointing from , simply equals . , since it takes no effort to stay in . For all other vertices, , which means that the path with minimum from to is unknown. 22For computational purposes, this default weight was traditionally a very large number. However, IEEE 754 floating standard permits values of .
Let denote the predecessor of , which is the previous vertex in a shortest path that can be used to back to the source. for all vertices incident on edges pointing from .
Find a vertex in (i.e., an unexamined vertex) that minimizes . If there is more than one with minimum weight, any one of them is an acceptable value of .
Let , i.e., mark as examined.
For each vertex such that an edge leads from to , compare the value of to , a value that will be called .
If is smaller than the value , then let and . This incremental way of finding shorter paths is called edge relaxation.
Otherwise, do nothing.
Repeat previous step until , that is, when all vertices have been examined.
After the last iteration, for any vertex where is not , the shortest path from to can be found repeated application of to until it yields . That is, the vertices in the path, in reverse , are .
Notice that there is no guarantee that this finds any shortest paths from . It simply finds whichever shortest paths do exist. In particular, when has an out-degree of zero, then all other vertices will simply be marked as examined without any changes in for any value of ; 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 equal the value of in the th iteration of the , where initially and = . Let denote the weight of the shortest path from to , given the knowledge of . Then
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 .
[TODO: more on algorithmic complexity]
|Title||The Real History of Getting Settled To Accomplish Studies|
|Date of creation||2013-11-27 10:59:45|
|Last modified on||2013-11-27 10:59:45|
|Last modified by||(0)|
|Synonym||shortest path algorithm|