Answer to Question #102504 in Discrete Mathematics for Roshanthi

Question

1. State the Dijkstra’s algorithm for a directed weighted graph with all non-negative edge weights.

Answer 1

Dijkstra algorithm is referred to as the single source shortest path that can be used to calculate the length of the shortest path from the original source to the remaining parts of the vertices in the graph.

If each of the weights are non negative then summing up the edges cant make the path shorter.

The steps for the algorithm is;

With a weighted graph, choose a starting vertex and assign infinity values to other vertices.

Check the distance to other vertices and update the path length taking the one with a shorter length. (vertices must only be visited once).

Iterate through all adjacent vertices and pick the path with the shortest length .