Edge Weight Requirement for Dijkstra's Algorithm

Dijkstra's algorithm finalizes each vertex's distance once it is popped from the priority queue.

Think about what could happen to a finalized distance if a later negative edge were discovered.

1. 1. Explain the greedy assumption

   Dijkstra's algorithm assumes that once a vertex is popped with the smallest tentative distance, no other path could possibly improve on it, since all other tentative distances are at least as large and edges only add nonnegative amounts.

2. 2. Show negative weights break this

   If a negative edge existed, a path through an already-finalized vertex could later produce a shorter distance, breaking the greedy finalization; hence edge weights must be nonnegative.

Answer: Edge weights must be nonnegative.