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.


Algorithm start-up
The outgoing arc A-B is released, the distance is 15, 15 being a better value than infinity we update the B label with 15
The outgoing arc A-C is released the distance 4 being better than the infinity we update the label of the top C
The next top of the algorithm is the one that is not yet visited and has the label with the lowest value. Here it is the c top with the value 4.On r
eleases the outgoing arc C-E, the distance calculated from the top A is 4 – 11 – 15. 15 being better than infinity we update the label of the top E.
The outgoing Arc C-D is released, the distance calculated from the top A is 4 – 2 – 6. 6 being better than infinity we update the label of the top D.

In the next step we visit the summit D because its value is the lowest of the g
raphOn releases the outgoing arc D-E and calculates the distance from the top A which is equal to 9 or a distance shorter than 15 (calculated at the prev
ious stage)We then deselect the arc C-E which was previously calculated as the best route to go from A to E and one updates the E summit with the
value 9.The E summit is ensued treated, there is no outgoing arc so there is no update.
The B-top is processed: the outgoing B-E arc is released, the distance of 15 -5 -20 being higher than the value of 9 of the E summit there is no update and the algorithm ends.

Leave a Reply

Your email address will not be published.