Dijkstra’s algorithm uses a greedy approach to solve the single-source shortest path (SSSP) problem in a weighted directed graph.

Question:

Dijkstra’s algorithm uses a greedy approach to solve the single-source shortest path (SSSP) problem in a weighted directed graph.

a) Write down Dijkstra’s algorithm and explain the running time complexity. Explain how the choice of data structure used affects the time complexity in the Dijkstra algorithm.

b) Bellman-Ford algorithm also solves the SSSP problem. Write down two advantages of Dijkstra’s over Bellman Ford’s.

c) Both Bellman-Ford and Dijkstra can be extended to solve all pair shortest paths (APSP) problems. What would be the worst-case time complexity for each of these?

Summary:

• The time complexity of dijkstra algorithm is O(V²). Its time complexity will be affected by the data structure used, as it gives time complexity O(E log V) on using the binary heap, while it gives O(V²) using a graph.
• Bellman-Ford works for negative weights also, and it can check the existence of a negative cycle. Dijkstra’s algorithm has better time complexity.
• Johnson’s algorithm uses both Dijkstra’s and Bellman-Ford to find all pair’s shortest paths.

Explanation:

1. a) Dijkstra’s algorithm:

• Allocate memory for a set named shortest path tree set. It keeps track of the vertices which are processes and are included in the shortest path tree. That means whichever is inside this set, its shortest path is already finalized.
• Assign a distance to all the vertices from the source node. The distance to itself is 0 and to other nodes is INFINITY.
• While SPTset doesn’t have all the vertices inside it:

1. Pick the vertex V which is not SPTset and that which has the minimum value of distance.
2. Add the vertex V to the SPTset.

• Then, expand all the nodes of ‘v’ and those which are already traversed but not in SPTset check if they get minimum distance via vertex ‘v’. If yes, then update their distance value, otherwise make it remain as such.

An example of the Dijkstra algorithm is:

The above algorithm has a time complexity of O(V^2), but it can also be reduced to O(E log V) by using a binary heap.

Here, V represents the number of vertices and E represents the number of edges.

• The choice of data structure does affect the algorithm. On using a graph data structure the time complexity of the algorithm is O(v^2), but by using the data structure Binary Heap, one can reduce its time complexity to O(E log V).

Thus, the choice data structure matters a lot in the case of this algorithm.

b) Advantage of Dijkstra algorithm over Bellman-Ford algorithm:

• The major advantage of Dijkstra’s algorithm is its time complexity which is O(E log V) which is less compared to the time complexity of the Bellman-Ford Algorithm which is O(VE).

Advantages of Bellman-Ford algorithm over Dijkstra’s:

• • It can handle negative weights, which is its major advantage over Dijkstra’s algorithm. Bellman-Ford algorithm handles both the directed and undirected graphs with non-negative weights. But it can handle directed graphs with negative weights too.
  • The bellman-Ford algorithm helps to check the existence of negative cycles in the graph.

c) Johnson’s algorithm is the all Pair Shortest Path (APSP) algorithm which uses both Dijkstra’s and Bellman-Ford algorithms. The worst-case time complexity of Johnson’s algorithm is O(V² log V + VE).

Also, read the Given below-defined UML class diagram.