Wing
Graph Algorithms
Dijkstra's Shortest Path
Edsger W. Dijkstra, 1956
A greedy algorithm that finds the shortest path between nodes in a weighted graph, visiting the nearest unvisited node at each step.
Kruskal's Minimum Spanning Tree
Joseph Kruskal, 1956
Builds a minimum spanning tree by sorting edges by weight and adding them if they don't create a cycle.
Bellman-Ford Algorithm
Richard Bellman & Lester Ford Jr., 1958
Finds shortest paths from a source by repeatedly relaxing all edges, handling negative weights unlike Dijkstra's.
Floyd-Warshall All-Pairs Shortest Paths
Robert Floyd, 1962
Computes shortest paths between all pairs of nodes by iteratively considering each node as an intermediate.
Topological Sort (Kahn's Algorithm)
Arthur Kahn, 1962
Linearly orders vertices of a directed acyclic graph so that every edge points from earlier to later.
Gale–Shapley Stable Matching
David Gale & Lloyd Shapley, 1962
Pair two sides with preferences so no two would both prefer each other over their assignment.
Disjoint-Set Union (Union–Find)
Bernard A. Galler & Michael J. Fischer, 1964
Maintains partitioned elements with union-by-rank merges and amortized‑fast canonical representatives.
Bidirectional Search
Nichols (folklore), 1965
Two simultaneous breadth-first waves—one from the start, one from the goal—meet near the middle to halve explored volume.
Edmonds' Blossom Algorithm
Jack Edmonds, 1965
Finds a maximum matching in general graphs by shrinking odd cycles (blossoms).
A* Search
Peter Hart, Nils Nilsson & Bertram Raphael, 1968
An informed search algorithm that uses a heuristic to efficiently find the shortest path on a grid or graph.
Tarjan Strongly Connected Components
Robert Tarjan, 1972
A single DFS with an auxiliary stack records discovery times and lowlinks to peel off SCCs as roots close.
Articulation Points (Tarjan)
Robert Tarjan, 1972
Single DFS pass records discovery times and lowlinks to expose cut vertices whose removal disconnects the graph.
Hopcroft–Karp Bipartite Matching
John Hopcroft & Richard Karp, 1973
Blocks shortest augmenting paths in phases—layered BFS in the auxiliary graph plus disjoint DFS augmentations.
Bridges (Tarjan DFS)
Robert Tarjan, 1974
One depth-first traversal in an undirected graph flags tree edges whose subtree has no back edge above the parent.
Johnson's Algorithm
Donald B. Johnson, 1977
Runs Bellman-Ford once to reweight edges, then Dijkstra from every vertex for all-pairs SP.
Kosaraju–Sharir SCC
Micha Sharir / S. Rao Kosaraju, 1978
Two depth-first passes: order by finishing times on G, then peel components on the reversed graph.