Question 1

+3−0Single correct

Consider the following strategy to solve the single source shortest path problem with positive integer edge weights from a source vertex s:
Replace each edge with weight w by w edges of weight 1 connected by new intermediate nodes. 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 statement is true?

A.
This strategy will not solve the problem correctly.
B.
This strategy will only work if the graph is acyclic.
C.
This strategy will solve the problem correctly and is as efficient as Dijkstra’s algorithm.
D.
This strategy will solve the problem correctly, but is not as efficient as Dijkstra’s algorithm.

Question 1

+3−0Single correct

A.
This strategy will not solve the problem correctly.
B.
This strategy will only work if the graph is acyclic.
C.
This strategy will solve the problem correctly and is as efficient as Dijkstra’s algorithm.
D.
This strategy will solve the problem correctly, but is not as efficient as Dijkstra’s algorithm.

Question 1

Report a problem

Submit this paper?

Instructions

Question 1

Report a problem

Submit this paper?

Instructions