The question is on dijkstra's algorithm. It states:
Suppose we change line 4 of Dijkstra’s algorithm to the following.
4 while |Q| > 1 . This change causes the while loop to execute |V| - 1 times instead of |V | times. Is this proposed algorithm correct?
The answer should be: No, the proposed algorithm is not correct. Dijkstra's algorithm is designed to find the shortest path from a source vertex to all other vertices in a graph. The loop in Dijkstra's algorithm is meant to iterate over all vertices in the graph, and the loop's exit condition is when all vertices have been visited.
Changing line 4 to "while |Q| > 1" means that the loop will exit prematurely as soon as there is only one vertex left in the queue. This will cause the algorithm to miss visiting some vertices, and as a result, it may not find the correct shortest path from the source vertex to all other vertices in the graph. This may result in some vertices not being explored at all.
Can I submit a pull request with the suggested changes?
walkccc
commented
1 year ago
The question is on dijkstra's algorithm. It states: Suppose we change line 4 of Dijkstra’s algorithm to the following. 4 while |Q| > 1 . This change causes the while loop to execute |V| - 1 times instead of |V | times. Is this proposed algorithm correct?
The current answer on the repository says: Yes it is correct. Full answer here: https://walkccc.me/CLRS/Chap24/24.3/
The answer should be: No, the proposed algorithm is not correct. Dijkstra's algorithm is designed to find the shortest path from a source vertex to all other vertices in a graph. The loop in Dijkstra's algorithm is meant to iterate over all vertices in the graph, and the loop's exit condition is when all vertices have been visited.
Changing line 4 to "while |Q| > 1" means that the loop will exit prematurely as soon as there is only one vertex left in the queue. This will cause the algorithm to miss visiting some vertices, and as a result, it may not find the correct shortest path from the source vertex to all other vertices in the graph. This may result in some vertices not being explored at all.
Can I submit a pull request with the suggested changes?