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

This answer is restricted. Please login to view the answer of this question.

Login Now

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 vthen it holds following steps:

  1. Initialize the distance field to 0 for v0 and to for each of other vertices.
  2. Enqueue all the vertices into a propriety queue Q with highest propriety being the lowest distance field value.
  3. Repeat step 4-10 until Q is empty
  4. The distance and back reference fields of every vertex that is not in Q are correct.
  5. Dequeue the highest priority vertex in v
  6. Do step 7-10 for each vertex w that are adjacent to v and in the propriety queue.
  7. Let S be the sum of the v’s distance field plus the weight of the edge from v to w
  8. If s less than w’s distance field, do step 9-10, otherwise go back to step 3
  9. Assign s to w’s distance field
  10. 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.

- Hamro CSIT - Hamro CSIT - Hamro CSIT - Hamro CSIT - Hamro CSIT

If you found any type of error on the answer then please mention on the comment or report an answer or submit your new answer.
Leave your Answer:

Click here to submit your answer.

Discussion
0 Comments
  Loading . . .