Question

Devise an algorithm for finding the second shortest path between two vertices in a simple connected weighted graph.

Short answer

It found that the second case may be that it doesn’t exist.

Step-by-step solution

Step 1:Finding the second shortest path

In order to find the simple shortest path first,

It needs to find out the shortest path between\(a\)to\(z\)(By the use of Dijkstra’s algorithm).

Then consider for each of the edges e in the path of one by one,

Then let omit e from the graph and again try to find a shortest path between a to z in the graph that remains after omission.

It even ensures that whether no such path exists.

Conclusion

Therefore, the second shortest path from \(a\)to\(z\)is a path of minimum length among all the paths so found and the second case may be that it doesn’t exist.