79296151

Date: 2024-12-20 04:14:51
Score: 1
Natty:
Report link

This is because:

  1. If negative weight edges exist, the greedy strategy may fail;
  2. After determining a vertex's shortest path, a shorter path might be found through negative weight edges, violating the algorithm's basic assumption: confirmed shortest paths won't be updated

For example, in the graph below, there's a negative weight edge CE with weight -13. The actual shortest path to E is 1 (shown by red arrows), but the algorithm calculates it as 10:

Error negative weight Dijkstra case

For graphs with negative weight edges, other algorithms (such as the Bellman-Ford algorithm) must be used to solve the shortest path problem.

If you want to see Dijkstra calculate the shortest path step by step, you can experience it on my Dijkstra algorithm visualization page.

Reasons:
  • Contains signature (1):
  • Long answer (-0.5):
  • No code block (0.5):
Posted by: selfboot