Dijkstra’s Algorithm assumes that all edge weights are non-negative. This assumption allows the algorithm to “lock in” the shortest path to each node as it discovers them, without needing to revisit or update paths. With negative weights, though, there’s a chance that a shorter path to a node could be discovered later, which breaks Dijkstra’s approach.
To dive deeper:
- Dijkstra’s Algorithm picks the smallest known path to the next node, but if there’s a negative weight edge, a previously visited node could later have an even shorter path.
- Negative cycles (if any) cause the algorithm to loop indefinitely because each pass makes the path “cheaper.”
0 Comments