the greedy view of Dijkstra

You want the shortest road distances from your home town to every other town, where roads have nonnegative lengths. Dijkstra's algorithm finds them, and at heart it is greedy: it repeatedly declares the closest still-unfinished town to be settled — fixing its shortest distance forever — and never revisits that decision. The leap of faith is that the nearest unsettled town can be finalized with no further information.

Maintain a tentative distance to every vertex, starting at 0 for the source and infinity elsewhere. Repeatedly do the greedy step: among vertices not yet finalized, pick the one with the smallest tentative distance, finalize it, and 'relax' its outgoing edges — for each neighbor, if going through this vertex is shorter, lower the neighbor's tentative distance. Why is finalizing the nearest unsettled vertex safe? Suppose its true shortest path were shorter than its current tentative value. That path must leave the finalized region somewhere, and the first vertex it reaches outside is an unfinalized vertex whose tentative distance is already at least as large (greedy picked the smallest). Since all edge lengths are nonnegative, the rest of the path only adds length, so the path cannot be shorter — contradiction. This is a 'greedy stays ahead' style invariant: every finalized vertex holds its true shortest distance.

Dijkstra is the shining example of a greedy algorithm whose correctness leans entirely on a sign assumption. With a negative edge, the argument collapses: a later, lightly-weighted detour through a negative edge could undercut a distance you already froze, so the greedy 'finalize the nearest' step becomes wrong — you would need Bellman-Ford instead. The detailed relaxation machinery, the priority-queue implementation, and the negative-weight handling live in the dedicated shortest-paths field; the point here is simply that Dijkstra is greedy, and exactly why nonnegativity is the hinge that makes its greed correct.