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

Login NowThe 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 v_{0 }then it holds following steps:

- Initialize the distance field to 0 for v
_{0}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.

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.

Click here to submit your answer.

HAMROCSIT.COM

## Discussion