Topic: Graph algorithms (All edges in shortest paths)

Instructions : Use the algorithms such as DFS, Explore, BFS, Dijkstra's (using min-heaps), Strongly Connected Components (SCC), Floyd-Marshall, Prim's MST, Topological Sort, Kruskal's MST, Bellman-Ford, and Union by Rank as a blackbox subroutine for your algorithm. Make sure to explain the algorithm in words (no pseudocode!), explain the correctness of the design, and state and analyze its running time in big-O notation.

 

Answer format (Template):

a) Step 1: 

Step 2:

Step 3:

b) Correctness

c) Runtime analysis

Question: Given an undirected graph G = (V,E) with positive edge weights and two nodes s,t ∈ V , design an efficient algorithm to determine the set of all edges that lie on at least one shortest path from s to t.