Illustrate the Dijkstra’s Algorithm to find the shortest path from source node to destination node with an example.

Question

Illustrate the Dijkstra&#8217;s Algorithm to find the shortest path from source node to destination node with an example.

Suresh Chand · Accepted Answer

The Dijkstra’s algorithm finds the shortest path from a particular node, called the source node to every other node in a connected graph. It produces a shortest path tree with the source node as the root. It is profoundly used in computer networks to generate optimal routes with the aim of minimizing routing costs. Algorithm: Precondition: G = (V, w) is a weighted graph with initial vertex v0 then it holds following steps: Initialize the distance field to 0 for v0 and to for each of other vertices. Enqueue all the vertices into a propriety queue Q with highest propriety being the lowest distance field value. Repeat step 4-10 until Q is empty The distance and back reference fields of every vertex that is not in Q are correct. Dequeue the highest priority vertex in v Do step 7-10 for each vertex w that are adjacent to v and in the propriety queue. Let S be the sum of the v's distance field plus the weight of the edge from v to w If s less than w's distance field, do step 9-10, otherwise go back to step 3 Assign s to w's distance field Assign v to w's back reference field. Below is a directed weighted graph. We will find shortest path between all the vertices using Dijkstra’a Algorithm.

Illustrate the Dijkstra’s Algorithm to find the shortest path from source node to destination node with an example.

Leave your Answer:

Hits Counter

Question

Illustrate the Dijkstra’s Algorithm to find the shortest path from source node to destination node with an example.

Leave your Answer: