Dijkstra Shortest Path Algorithm

The Dijkstra algorithm is a very popular and useful algorithm, which is used for searching the shortest path between two vertices, or between the start vertex and all other vertices at all. This algorithm isn't perfect at all, but it returns the shortest path always for a weighted graph with positive weights (or paths). Yes, sometimes edges can have a negative value of 'weight'.

This is a step-by-step algorithm to visit all the nodes, and every time update the minimum path from start to the current node. So for each vertex, we have a dist[vertex] tag – minimum path length which is found now.

Initially, the start node has tag 0 and all the other nodes have tag inf.

The algorithm is next:

1. Select the current vertex v. It should be the closest one (with minimum value of dist[v]) and not visited yet.
2. If there is no such a vertex v or the distance to it is equal to inf, we should stop the algorithm. There is no way to access the other vertices.
3. For each neighbor of current node v update tags: dist[neighbor] = min(dist[neighbor], dist[v] + g[v][neighbor]) - distance has the minimum value now.
4. Stop if all nodes are visited.

On the gif, you can see the demo of how it works. After completing the task, the graph from a gif is created, and you can follow it step-by-step.