Hello Friends, In this blog post, I am going to let you know about an interesting shortest path algorithm which is also known as the Dijkstra Algorithm.
This ‘Dijkstra algorithm’ technique is widely used in many forms because it is simple and easy to understand. The idea is to make a graph of the subnet, with each node of the graph representing a router and each arc of the graph representing a communication line(often known as a link).
For selecting a route between a given pair of routers, the algorithm just finds the shortest path between them on the graph. One method of measuring path length is the number of hops.
Using this metric, the paths ABC and ABE are equally long as shown in fig1. Another metric is the geographic distance in kilometers, in which case ABC is much longer than ABE.
Several other metrics are also possible besides hops and physical distance. As an example, each arc could be labeled with the mean queueing and transmission delay for some standard test packets determined by hourly test runs.
The shortest path is the fastest path with this graph labeling, rather than the path with the fewest arcs or kilometers. Generally, the labels on the arcs could be computed as a function of the distance, bandwidth, average traffic, communication cost, mean queue length, measured delay, and other factors.
Then the algorithm would compute the shortest path by changing the weighting function, measured according to any one of a number of criteria or a combination of criteria.
Many algorithm for computing the shortest path between two nodes of a graph are known. every node is labeled with its distance from the source node along the best-known path.
In starting, the paths are not known, therefore all nodes are labeled with infinity. As the algorithm proceeds and paths are obtained, the labels may change, reflecting better paths.
A label may be either permanent or tentative. All labels are tentative in starting. When it is discovered that a label tells the shortest possible path from the source to that node, it is made permanent and never changed thereafter.
For illustrating the working of labeling algorithm see at the weighted undirected graph of fig1(a) where the weights represent distance. For finding the shortest path from A to D.
We start out by marking node A as permanent, denoted by a filled-in circle. Then, each of the nodes adjacent to A (the working node), relabeling each one with the distance to A.
Whenever a node is relabeled, it is also labeled with the node from which the probe was made, therefore the final path can be constructed later. After examining each of the nodes adjacent to A,…
all the tentatively labeled nodes are examined in the whole graph and made the one with the smallest label permanent as shown in fig1(b). This one is the new working node.
Now, starting is done from B and all nodes adjacent to it are examined. If the sum of the label on B and the distance from B to the node being considered is less than the label on that node, a shorter path is obtained, therefore the label is relabeled.
When all the nodes adjacent to the working node have been inspected and the tentative labels changed if possible, the whole graph is searched for the tentatively labeled node with the smallest value.
This node is made permanent and is the working node for the next round. The first five steps of the algorithm are shown in fig1.
In the case of any queries, you can write to us at email@example.com we will get back to you ASAP.
Hope! you would have enjoyed this post about ‘Dijkstra’s Algorithm for the shortest path’.
Please feel free to give your important feedbacks in the comment section below.
Have a great time! Sayonara!
- Addon Domain vs SubDomain In Hindi. Addon domain और subdomain हिंदी में
- Fundamentals Of C In Hindi
- Preprocessor Directives Of C In Hindi.
- History And Introduction of C Language In Hindi. C language हिंदी में
- Determine and explain if the following binary tree is Heap, BST, Height balance tree, Complete binary tree full binary tree?
- B-Tree Example In Data Structure.
- Kruskal Algorithm In Hindi In Data Structure. Kruskal Algorithm हिंदी में.
- Prim’s Algorithm In Hindi In Data Structure. Prim’s Algorithm हिंदी में
- Sorting Algorithm And Their Time Complexity In Data Structure.
- Shell Sort In Data Structure.