Bellman-Ford generalized shortest-path computation to weighted graphs with negative edges and added a decisive test for negative cycles, using repeated relaxation rather than a greedy frontier.
Prim and Kruskal independently showed how local greedy edge choices can provably construct a minimum spanning tree, one growing a connected tree and the other merging a forest.
Ford and Fulkerson turned network capacity into an augmenting-path algorithm and a duality theorem: keep pushing additional flow until no source-to-sink residual path remains.
Hopcroft and Karp accelerated bipartite matching by finding many shortest augmenting paths in each phase instead of one path at a time, achieving O(E√V) time.
Robert Tarjan transformed depth-first search from a traversal routine into a design method for linear-time graph algorithms, data structures, planarity, connectivity, and set operations.
Edsger Dijkstra's shortest-path algorithm repeatedly finalizes the nearest reachable vertex, turning weighted-route search into a disciplined greedy process with a provable invariant.