Dots, and the lines between them.

A graph is just dots and lines — but those dots and lines can model road networks, social networks, dependency chains, and pretty much anything with "things" and "connections between things". This site covers the vocabulary, the major graph types, and two of the most-asked-about shortest-path algorithms.

  • Terminology — node, edge, weight, degree, and the rest of the vocabulary.
  • Types of Graphs — directed vs undirected, weighted, trees, bipartite…
  • Dijkstra's — shortest paths from one source, one step at a time.
  • A* — Dijkstra's plus a hunch about where the goal is.

Graph Terminology

Node (vertex)
A single point in the graph — A through F. "Vertex" means the same thing; we'll stick with "node".
Edge
A connection between two nodes, e.g. B–E.
Weight
A cost attached to an edge — distance, time, price, whatever you're optimising for.
Degree
The number of edges touching a node. B has degree 4.
Path
A sequence of edges connecting one node to another, e.g. A → D → E → F.
Adjacent
A and D are adjacent; A and F are not.
Connected graph
Every node can reach every other node, possibly via several hops.
Q1. What's the degree of node E in the graph above?
E connects to B, D, C and F — degree 4.

Types of Graphs

The same handful of nodes, rearranged to show what actually changes.

Undirected

Edges have no direction — if P connects to Q, you can travel either way.

Directed

Edges point one way only. Also called a digraph.

Weighted

Every edge carries a cost. Dijkstra and A* both need this.

Unweighted

Every edge counts the same — effectively, weight 1.

Tree

Connected and acyclic: exactly one path between any two nodes.

Cyclic

Contains at least one cycle — a path that loops back on itself.

Complete graph

Every node is directly connected to every other node.

Bipartite

Nodes split into two groups; edges only run between groups, never within one.

Q1. Is the main graph (from the Terminology tab) cyclic or acyclic?
Cyclic — for example B–D, D–E, E–B forms a loop back to where it started.

Dijkstra's Algorithm

Dijkstra's algorithm works out the shortest distance from one starting node to every other node in a weighted graph. It works by repeatedly picking whichever unfinished node is currently closest, locking in its distance as final, and then checking whether going through it gives a shorter route to its neighbours.

This only works if every edge weight is zero or positive. With a negative edge, a node you've already marked "finished" could later turn out to have a shorter route through it — so the algorithm can lock in the wrong answer. If your graph has negative weights, use Bellman–Ford instead.

Step by step

  1. Give the starting node a distance of 0, and every other node a distance of infinity (unknown).
  2. Look at all the unfinished nodes, and pick whichever one currently has the smallest distance.
  3. Mark that node as finished — its distance is now final and won't change again.
  4. Check each of its neighbours: does going through this node give them a shorter distance than they currently have? If so, update it, and note which node you came from.
  5. Repeat until every node is finished.
  6. To find the actual route, not just the distance, trace back through those "came from" notes, from the destination to the start.
If you already know breadth-first search: Dijkstra's algorithm is BFS generalised to weighted graphs. Give every edge the same weight, and the two finish nodes in exactly the same order.

Worked example: shortest paths from A

Tracing the algorithm on the graph from the Terminology tab, one row per node finished — the boxed value is the distance locked in on that row:

StepFinishedABCDEF
1A04∞2∞∞
2D03∞25∞
3B03825∞
4E037256
5F037256
6C037256

F finishes at distance 6. Tracing back which node led to which gives the route A → D → E → F — see it happen step by step on the Walkthrough tab.

How fast is it?

Every node is finished exactly once, and every edge is checked at most once. What changes the speed is how quickly you can find "the unfinished node with the smallest distance" each time:

  • Scanning the list each time — simple, but slower on large graphs. This is the version usually traced by hand in exams.
  • Using a priority queue (min-heap) — faster on large graphs. This is what real routing software uses.

Where you'll see this

Dijkstra's algorithm (or a close variant) underpins link-state routing protocols like OSPF, and shows up anywhere you need "cheapest route from here to everywhere" — GPS navigation, flight and train connection search, and network packet routing.

Edsger Dijkstra designed this algorithm in 1956, without a computer, in about twenty minutes over coffee with his fiancée — he wanted something simple enough to explain but impressive enough to show off a new machine. He didn't publish it until 1959, and it's still one of the most-cited algorithms in computer science.

Once you've followed the worked example in Info, try tracing Dijkstra's algorithm yourself on a fresh graph.

Trace it yourself

Pick a graph below. Use the two lists to track which nodes you've discovered and which you've finalised — add a node's pill to a list yourself, and click a pill to strike it through once it's no longer relevant (e.g. superseded, or finalised). The table starts completely blank: click any cell to select it, then type a value below and add it (use the ∞ button for a starting "infinite" distance) — row 1 is the node you start from, and each row after that is the next node you finalise, in order. The old value in a cell stays, crossed out, so you can see the trail of improvements, with the newest pill as the live answer. Use Check to mark the live values, or Reveal if you get stuck.

Source node: A

Nodes Discovered

Visited

Click a table cell to add a value to it.

Coming soon — this will practise Dijkstra's algorithm using the "global initialisation" method, where every node starts with a distance already written in (0 for the source, infinity for everything else), rather than discovering nodes one at a time.

A* Search

A is Dijkstra's algorithm with a hint. Alongside the distance travelled so far (g), it adds a heuristic estimate of the distance still to go (h), and always expands the node with the smallest f = g + h. A good heuristic — one that never overestimates — means A finds the same shortest path as Dijkstra, usually after looking at far fewer nodes.

Goal is F. Compare the number of expanded nodes against the Dijkstra tab.

Q1. Why does A* usually expand fewer nodes than Dijkstra?
Because the heuristic gives a lower-bound estimate of the remaining distance, so A* prioritises nodes likely to be on the shortest path to the goal instead of exploring uniformly outward.