Graph Algorithm Laboratory
Run 14 graph operations on a list of edges and see the answer drawn on the graph. It covers shortest paths (Dijkstra, A*, Bellman–Ford, Floyd–Warshall), minimum spanning trees, maximum flow, bipartite matching, a travelling-salesman tour, topological order, dependency levels, cycles, components, colouring and the adjacency matrix.
How to Use
- List the edges, one per line:
A Bfor an edge, orA B 5to give it a weight (a distance, cost or capacity). Node names can be any words. - Choose Undirected or Directed. Topological sort and the dependency resolver need directed edges, where
A Bmeans A comes before B. - Pick an algorithm. The path and flow algorithms use the source and target boxes, the TSP tour uses the source as its start, and the rest run on the whole graph.
- Read the answer in the text panel and on the graph: paths, trees, tours and matched pairs in pink, components and dependency levels as node colours, and distances or positions as labels above the nodes.
- The example chips load a ready-made case for each algorithm, such as Bellman–Ford with a negative edge or a getting-dressed topological sort.
Worked Example
Dijkstra on the default graph, from A. A starts at 0 and its neighbours get B = 7, C = 9 and F = 14. The nearest unvisited node is B (7), which offers nothing better for C and gives D = 22. Next is C (9): through it F drops to 11 and D to 20. From F (11), E becomes 20. So the distances are B 7, C 9, F 11, D 20 and E 20, and the shortest route from A to E is A → C → F → E = 20.
Maximum flow. In the directed network S→A 3, S→B 2, A→B 1, A→T 2, B→T 3, the most that can flow from S to T is 5. Nothing more can get out of S, whose two edges carry 3 + 2 = 5: that is the minimum cut, and by the max-flow min-cut theorem the two numbers are always equal.
The common mistake: counting edges instead of adding weights. A → F → E uses only 2 edges, but its weight is 14 + 9 = 23. A → C → F → E uses 3 edges and weighs 9 + 2 + 9 = 20. Fewest hops is the shortest path only when every edge has the same weight.
Show Work
Formulas
From Königsberg to Routing Tables
Graph theory began in 1736, when Leonhard Euler proved that nobody could walk through Königsberg crossing each of its seven bridges exactly once. He reduced the city to land masses joined by bridges, the first graph, and showed that such a walk needs at most two land masses with an odd number of bridges; Königsberg had four.
Most of the algorithms here date from the computer age. Edsger Dijkstra designed his shortest-path method in 1956, in about twenty minutes at a café in Amsterdam, and published it in 1959. Joseph Kruskal published his spanning-tree method in 1956, and L. R. Ford Jr. and D. R. Fulkerson the max-flow min-cut theorem the same year. Richard Bellman described his shortest-path algorithm in 1958, Robert Floyd and Stephen Warshall published the all-pairs method in 1962, Peter Hart, Nils Nilsson and Bertram Raphael introduced A* in 1968, and Jack Edmonds and Richard Karp gave their breadth-first version of max flow in 1972.
About This Tool
This lab runs 14 operations on the same typed list of edges, so you can switch from shortest path to spanning tree to max flow without re-entering anything, and it draws each answer on a force-directed layout of the graph. It handles directed and undirected graphs, weights including negative ones where the algorithm allows them, and any node names. The TSP tour is a heuristic and the colouring a greedy upper bound; the other results are exact.
Everything runs in your browser; nothing is uploaded.
Related tools: Optimization Solver, Linear Algebra Lab, and Permutation and Combination Calculator.
Frequently Asked Questions
When should I use Bellman–Ford or Floyd–Warshall instead of Dijkstra?
Dijkstra is the fastest but needs weights of 0 or more, and this tool stops with a message if it meets a negative one. Bellman–Ford accepts negative weights and reports a negative cycle if there is one: in the directed example, A to D is 3 along A → B → C → D, using the −3 edge. Floyd–Warshall finds every pair at once; in its example C to D is 3 by way of B, not the direct edge of 7.
How is the minimum spanning tree chosen?
By Kruskal’s method: sort the edges by weight and keep each one that joins two parts not yet connected. In the default graph that keeps C–F (2), D–E (6), A–B (7), A–C (9) and E–F (9), 5 edges linking all 6 nodes for a total of 33, against 83 for every edge. If the graph is in pieces, the result is a minimum spanning forest and the tool says how many pieces there are.
Is the travelling-salesman tour optimal?
Not always: exact TSP is NP-hard, so the tool builds a nearest-neighbour tour and improves it with 2-opt swaps, using shortest-path distances between nodes. In the 4-city example the nearest-neighbour tour A → B → C → D → A is 85; 2-opt reverses part of it to A → B → D → C → A, which is 80 and is the best possible tour for those cities. On larger graphs it is usually close to the optimum but not guaranteed.
How is the maximum flow found?
With Edmonds–Karp: repeatedly find the shortest path from source to sink that still has spare capacity, push as much as it allows, and stop when none is left. In the example network the maximum flow from S to T is 5, which matches the cheapest cut, the two edges leaving S with capacities 3 and 2. Edge labels show flow / capacity.
What is the difference between topological sort and the dependency resolver?
Both need a directed graph without cycles. Topological sort gives one valid order, breaking ties alphabetically: the getting-dressed example gives shirt, socks, tie, underwear, pants, belt, jacket, shoes. The dependency resolver groups items into steps that can run in parallel: the bread example takes 6 steps, and step 1 is flour, oven, water and yeast together. If there is a cycle, it lists the items that can never be reached.
How do I use the Graph Algorithm Laboratory?
Simply type your numbers and read the result, which refreshes the instant you change something. There is nothing to submit and nothing to wait for.
Do I need to install or sign up for anything?
Not at all — it runs in the browser with nothing to install and no account. After it loads once, it even works without an internet connection.
Is my information private?
Yes. Everything happens in your browser. Nothing you type is sent to a server or saved anywhere.
Common Use Cases
Cabling and pipes
The spanning tree of the default graph joins all 6 nodes with 33 units of the 83 available.
Routing
Shortest route from A to E: 20, along A → C → F → E.
Project planning
The 9 items of a bread recipe resolve into 6 steps, with 4 able to start at once.
Assigning work
3 jobs, each open to 2 of 3 workers: all 3 can be filled with no one booked twice.
Delivery rounds
A 4-stop round trip of length 80 instead of 85.
Timetables
Graph colouring puts the 5 clashing exams of the example into 3 time slots.
Last updated: