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 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 outside the subgraph 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 is the minimum between the existing distance and that obtained by adding the weight of the arc to the weight obtained to reach the selected 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.