Graphs & networks
Edit a weighted graph and run shortest-path or spanning-tree algorithms. Every decision is recorded, and the finished working exports as .
- Shortest distance A → E: 10.
- Path: A → C → B → D → E.
- Visit A with tentative distance 0.
- Relax A \to B: 0 + 4 = 4, so d(B) = 4.
- Relax A \to C: 0 + 2 = 2, so d(C) = 2.
- Visit C with tentative distance 2.
- Relax C \to B: 2 + 1 = 3, so d(B) = 3.
- Relax C \to D: 2 + 8 = 10, so d(D) = 10.
- Relax C \to E: 2 + 10 = 12, so d(E) = 12.
- Visit B with tentative distance 3.
- Relax B \to D: 3 + 5 = 8, so d(D) = 8.
- Visit D with tentative distance 8.
- Relax D \to E: 8 + 2 = 10, so d(E) = 10.
- Visit E with tentative distance 10.
Algorithms
- Dijkstra finds the shortest path from one source, provided all weights are non-negative.
- Floyd–Warshall finds shortest distances between every pair of vertices.
- Kruskal builds a minimum spanning tree by taking edges in increasing weight and rejecting cycles.
- Prim grows a minimum spanning tree from a chosen start vertex by repeatedly taking the lightest crossing edge.
Critical path analysis and route inspection are the next graph methods in the queue; the current release covers the shortest-path and minimum-spanning-tree algorithms.
Reading the working
The adjacency matrix stores the weight on each edge; leave a cell blank when there is no edge. For an undirected graph the matrix is mirrored, so entering a weight once is enough.
Each algorithm reports its running state after every decision. The shortest-path algorithms show distance updates, while the spanning-tree algorithms show accepted and rejected edges and the running total.
Export
The tab previews the document and lets you copy or download the .tex source.