Answer to Question #272353 in Algorithms for Anu

Question

Formulate a shortest path algorithm and find the shortest paths from two vertices

(i) V0 and

(ii)𝑉₃ to the rest of the vertices in the following graph using Dijkstra’s single source

shortest path Algorithm.

Answer 1

Dijkstra's Algorithm allows you to calculate the shortest path between one node (you pick which one) and every other node in the graph.

description of the algorithm:

1. Mark your selected initial node with a current distance of 0 and the rest with infinity.
2. Set the non-visited node with the smallest current distance as the current node C.
3. For each neighbour N of your current node C: add the current distance of C with the weight of the edge connecting C-N. If it's smaller than the current distance of N, set it as the new current distance of N.
4. Mark the current node C as visited.
5. If there are non-visited nodes, go to step 2.