One algorithm for finding the shortest path from a starting node to a target node in a weighted graph is Dijkstra’s algorithm. The algorithm creates a tree of shortest paths from the starting vertex, the source, to all other points in the graph.
Dijkstra’s algorithm, published in 1959 and named after its creator Dutch computer scientist Edsger Dijkstra, can be applied on a weighted graph. The graph can either be directed or undirected. One stipulation to using the algorithm is that the graph needs to have a non-negative weight on every edge.
This is the basic algorithm used by programmers to count the shortest path from one node to every other node.
There many practical application of it in real life like using Dijkstra is used. Like it used in location applications to give us the shortest route from one point to another point.
We will now dive straight into the algorithm and see how it works.
We will be talking about a graph where,
The graph has the following:
• vertices, or nodes, denoted in the algorithm by v or u.
• weighted edges that connect two nodes: (u,v) denotes an edge, and w(u,v) denotes its weight. In the diagram on the right, the weight for each edge is written in gray.
This is done by initializing three values:
• dist, an array of distances from the source node s to each node in the graph, initialized the following way: dist(s) = 0; and for all other nodes v, dist(v) = ∞. This is done at the beginning because as the algorithm proceeds, the dist from the source to each node v in the graph will be recalculated and finalized when the shortest distance to v is found
• Q, a queue of all nodes present in the graph. At the end of the algorithm's progress, Q will be empty.
• S, an empty set, to indicate which nodes the algorithm has visited. At the end of the algorithm's run, S will contain all the nodes of the graph.
The algorithm proceeds as follows:
1. While Q is not empty, pop the node v, that is not already in S, from Q with the smallest dist (v). In the first run, source node s will be chosen because dist(s) was initialized to 0. In the next run, the next node with the smallest dist value is chosen from the Queue and this work keeps on happening.
2. Add node v to S, to indicate that v has been visited. (This is where we have reached minimum distance for that particular node ‘v’).
3. Update dist values of adjacent nodes of the current node v as follows: for each new adjacent node u,
• if dist (v) + w(u,v) < dist (u), there is a new minimal distance found for u, so update dist (u) to the new minimal distance value;
• otherwise, no updates are made to dist (u).
The algorithm has visited all nodes in the graph and found the smallest distance to each node. dist now contains the shortest path tree from source s.
This is the implementation in O(n*logn) and is a really efficient way to find the shortest paths using dijkstra.
This article is contributed by MD Zuhair
So that’s it for this article we will be coming up with our next article on further topics of Graph Theory very soon till then keep learning, keep coding, keep reading and keep improving !!
Happy Coding
By Programmers Army 😊