Graph Algorithms

A Note on Two Problems in Connexion with Graphs

E. W. Dijkstra

Gives an algorithm for the shortest path between two nodes and for a minimum spanning tree, both in time proportional to the square of the number of nodes.

Assumes graphs, and nothing else — under three pages, and it predates the notation now used to teach it

Depth-First Search and Linear Graph Algorithms

Robert E. Tarjan

Shows that depth-first search, run once, reveals a graph's biconnected components and strongly connected components in time proportional to its size.