Dijkstra's algorithm in a weighted and oriented graph in more than 128 words

For a source peak given in the graph, the algorithm looks for the shortest path between that node and all the others.

Here one uses a weighted graph, which is a graph in which each arc (case of a oriented graph) receives a weight. A weighted graph is therefore a special type of labeled graph in which the labels are numbers.

The weight of a chain or path is the sum of the weights of the arcs that make up the chain.

The algorithm enters a weighted graph and a summit from which it calculates distances, the steps are:

Initialization phase:

On all the tops, a label equal to infinity (or at the maximum possible length – 1) is positioned on all the tops.

The label is started on A to 0

Treatment phase:

We treat a summit (here we start with A)

We mark the summit as visited

We release the outbound arches from the summit, i.e. we try to update the value of the top-of-the-finish label by distance.

If the value of the road to the top of the finish is lower than the calculated, the top tag is updated with this total distance.

The next top to be treated is the one with the lowest weight.