EW Dijkstra (1930-2002) proposed in 1959 a algorithm (called Dijkstra's algorithm) which makes it possible to determine the shortest way between two vertices of a graph connected weighted. Dijkstra's algorithm is based on the following observation: once we determine the shortest path to a vertex v, then the paths that go from v to each of its adjacent vertices could be the shortest path to each of these neighboring peaks. Dijkstra's algorithm is an algorithm of dynamic programming gluttonous, he visits all possible solutions.
Dijkstra's algorithm takes as input a directed graph weighted by positive reals and a source vertex. This involves progressively building a subgraph in which the different vertices are classified in increasing order of their minimum distance from the starting vertex. The distance corresponds to the sum of the weights of the borrowed edges.
Initially, we consider that the distances from each vertex to the starting vertex are infinite except for the starting vertex for which the distance is 0. The starting subgraph is the empty set.
During each iteration, we choose outside the subgraph a vertex of minimum distance and we add it to the subgraph (it becomes a visited vertex). Then, we update the distances of the neighboring vertices of the added one (the vertices are marked). The update takes place as follows: the new distance from the neighboring vertex is the minimum between the existing distance and that obtained by adding the weight of the arc between neighboring vertex and vertex added to the distance from the added vertex.
We continue in this way until the subgraph is completely completed (or until the arrival vertex is selected). Example :
|distance||to A||to B||to C||to D||to E||to F||to G||to H||have||to J|
For practical reasons, the resolution of Dijkstra's algorithm only returns a vector containing the visited vertex, the list of predecessors (the already validated vertices) and the values of the shortest paths to all the other vertices. Which corresponds to a current line of the presented table. Using the left column, we can create a tree shortest paths from vertex A to all vertices.