retagged by
1,191 views
0 votes
0 votes

Consider the following strategy to solve the single source shortest path problem with edge weights from source s.

1. Replace each edge with weight w by w edges of weight 1 connected by new intermediate nodes

2. Run BFS(s) on the modified graph to find the shortest path to each of the original vertices in the graph.

 

Which of the following statements is correct?

  1. This strategy will solve the problem correctly but is not as efficient as Dijkstra's algorithm.
  2. This strategy will solve the problem correctly and is as efficient as Dijkstra's algorithm.s st
  3. This strategy will not solve the problem correctly.
  4. This strategy will only work if the graph is acyclic.
retagged by

1 Answer

Best answer
0 votes
0 votes

A. This strategy will solve the problem correctly but is not as efficient as Dijkstra's algorithm....

 

The size of the graph blows up according to the edge weights, but the strategy is otherwise correct....

selected by

Related questions

0 votes
0 votes
1 answer
2