E. W. Dijkstra (1930-2002) proposed in 1959 an algorithm which determines the shortest path between two vertices of a weighted connected graph. The algorithm is based on the following observation: once we determine the shortest path to a vertex v, then the paths that continue from v to each of its adjacent vertices could be the shortest path to each of those neighbour vertices. Dijkstra’s algorithm is a greedy dynamic programming algorithm, it visits all possible solutions.
The algorithm takes as input an oriented graph weighted by positive real numbers and a source vertex. It is a question of gradually building a subgraph in which the different vertices are classified in ascending order of their minimum distance to the starting vertex. The distance is 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, a vertex of minimum distance is selected (it becomes a visited vertex) outside the subgraph (from marked vertices) and added to the subgraph. Then, we update the distances of the vertices next to the one added. The update takes place as follows: the new distance from the neighboring vertex (becomes a marked vertex) is the minimum between the existing distance and that obtained by adding the weight of the arc to the weight obtained to reach the visited vertex.
This continues until you complete the subgraph completely (or until the selection of the end vertex if it exists). Example:
|distance||to A||to B||to C||to D||to E||to F||to G||to H||to I||to J|
For practical reasons, the resolution of the Dijkstra algorithm only returns a vector containing the visited vertex, the list of predecessors (the vertices already validated) and the values of the shortest paths to all the other vertices. Which corresponds to a current line of the table. Thanks to the left column, we can create a tree of shortest paths from vertex A to any vertices.