📖 Learning #13 December 2026 ~9 min read

Graph Theory & Algorithms — Dijkstra, A*, Minimum Spanning Trees and Force-Directed Layouts

Every map app, package delivery route, social network layout and circuit board traces back to graph algorithms. Seven interactive simulations take you from classic shortest-path search to the NP-hard travelling-salesman problem — and show the underlying mathematics step by step.

Shortest Paths

Edsger Dijkstra's 1956 algorithm visits nodes in order of cumulative cost from the source, guaranteeing optimality on graphs with non-negative edge weights. On a 1000-node grid it processes in milliseconds; on sparse real-world road networks it handles millions of nodes with suitable priority-queue tuning.

Search

Pathfinding — Dijkstra & A*

Draw obstacles on a grid and compare Dijkstra (explores uniformly outward) vs A* (guided by h(v)=‖v−goal‖ Euclidean heuristic). Visualise the frontier and closed set in real time.

Search

Maze Generation & Solving

Generate mazes via recursive backtracking, Prim's randomised MST, or Eller's row-by-row algorithm. Solve with BFS (shortest path), DFS (fast, non-optimal), or A*.

Dijkstra vs A* Complexity

Dijkstra: O((V + E) log V) with binary heap priority queue

A*: O(b^d) worst case; near O(E log V) with good heuristic h(v)

A* guarantee: if h(v) is admissible (h(v) ≤ true cost), result is optimal

f(v) = g(v) + h(v) where g = cost from start, h = heuristic to goal

Spanning Trees & Connectivity

A minimum spanning tree (MST) connects all nodes with minimum total edge weight and no cycles. Kruskal's algorithm sorts all edges by weight and uses a union-find structure; Prim's algorithm grows one tree from a seed node. Both yield the same MST but differ in performance on dense vs sparse graphs.

Graph

Minimum Spanning Tree

Add random nodes and watch Kruskal's and Prim's algorithms build the MST edge-by-edge. Union-find path compression illustrated; compare edge counts to the full clique.

Layout

Force-Directed Graph Layout

Fruchterman-Reingold layout algorithm — edges act as springs (Hooke's law), nodes repel via Coulomb force. Self-organising layout reveals clusters and peripheral nodes.

Combinatorial Optimisation

Some graph problems have no known polynomial-time algorithm. The Travelling Salesman Problem (TSP) — find the shortest tour visiting every node exactly once — is NP-hard. Yet approximations and heuristics work surprisingly well in practice.

Optimisation

Travelling Salesman Problem

2-opt and nearest-neighbour heuristics for TSP on 20–80 cities. Compare greedy insertion (fast, ~25% above optimal) vs simulated annealing (slower, near-optimal on 40 cities).

Classic

Sorting Algorithm Visualiser

Bubble, merge, quicksort, heapsort rendered as colour-coded bars. Inversion count displayed in real time; compare O(n²) vs O(n log n) wall-clock on n=50 to n=300 inputs.

ML

Decision Tree Learning

Interactive decision tree grown on configurable datasets using information gain (ID3) or Gini impurity (CART). Visualise splits at each depth, accuracy vs max-depth trade-off.

Why does A* outperform Dijkstra in practice? Dijkstra expands nodes in all directions equally. A* uses a heuristic h(v) to bias expansion towards the goal, exploring far fewer nodes. On road networks Dijkstra typically explores >50% of the graph; A* with Euclidean distance explores <5% — without sacrificing optimality.

Learning Paths

Classic Algorithms Track

  1. Sorting Algorithm Visualiser
  2. Pathfinding — Dijkstra & A*
  3. Maze Generation & Solving
  4. Minimum Spanning Tree

Advanced Graph Track

  1. Force-Directed Graph Layout
  2. Travelling Salesman Problem
  3. Decision Tree Learning

Algorithms Covered

Dijkstra A* Search BFS / DFS Kruskal MST Prim MST Union-Find 2-opt TSP Simulated Annealing Fruchterman-Reingold ID3 / CART Merge Sort Quicksort
Learning Algorithms Graphs Pathfinding Computer Science