Question

Let G(V, E) be a directed graph where every edge has weight as either 1, 2 or 5, what is the algorithm used for the shortest path from a given source vertex to a given destination vertex to get the time complexity of O(V+E)?

(a) BFS

(b) DFS

(c) Binary search

(d) Radix sort

I got this question in an interview.

My doubt stems from Different Path in a Graph in section Graphs of Discrete Mathematics

Answer 1

Right choice is (a) BFS

Best explanation: In BFS due to the least number of edges between two vertices and so if all the edges in a graph are of same weight, then to find the shortest path BFS can be used for efficiency. So we have to split all edges of weight 5 into two edges of weight 2 each and one edge of weight 1. In the worst case, all edges are of weight 1. To split all edges, O(E) operations can be done and so the time complexity becomes which is equal to O(V+E).