01Overview
In 1736 Euler proved that the seven bridges of Königsberg cannot all be crossed once: he abstracted vertices and edges and showed that the number of odd-degree vertices decides whether an Euler tour exists. It is regarded as the start of graph theory and of network science.
In the twentieth century graph algorithms became a core tool of computer science. Dijkstra gave shortest paths in 1956; Prim and Kruskal gave minimum spanning trees in 1957; Floyd solved all-pairs shortest paths in 1962. Max flow, bipartite matching and topological sorting underpin scheduling, networks and dependency management. Social networks, map navigation and compilers all still run these sixty-year-old algorithms.
02History
- 1736
Euler solves the seven bridges
Graph theory is born.
- 1956
Dijkstra's shortest paths
Single-source shortest paths with non-negative weights.
- 1957
Prim and Kruskal: minimum spanning trees
Two greedy strategies for the same problem.
- 1962
Floyd–Warshall
All-pairs shortest paths by dynamic programming.
- 1972
Edmonds–Karp max flow
Breadth-first search keeps it polynomial.
03Core concepts
Graph representations
Adjacency lists and matrices decide the cost of traversal and storage.
Shortest paths
Finding the cheapest route through a weighted graph.
Minimum spanning tree
n−1 edges connecting every vertex with the least total weight.
04Hands-on
Do it once — it beats reading it ten times
Run Dijkstra on a real map extract, then re-run it with negative weights and watch it break
05Self-check
Say it in your own words first, then open the answer. Whatever you cannot explain is what to review next.
Can you explain "Graph representations"?
Adjacency lists and matrices decide the cost of traversal and storage.
Can you explain "Shortest paths"?
Finding the cheapest route through a weighted graph.
Can you explain "Minimum spanning tree"?
n−1 edges connecting every vertex with the least total weight.
What problem did it solve, and why was there nothing better at the time?
Go back to the history section: how was this done before, and what did it cost?
If you had to build it today, how would you break it down?
Use the hands-on task above: write a plan of at most three steps before you start.
06Key people
Leonhard Euler
1707 – 1783
Solved the seven bridges and founded graph theory.
Edsger Dijkstra
1930 – 2002
Shortest paths, structured programming and semaphores.
07Further reading
- Introduction to Algorithms, Part VI
- Graph Theory