Imagine a team of explorers navigating a remote wilderness.
The wilderness is mapped as a network of checkpoints (nodes) connected by trails (directed edges), each with an associated cost — travel time, distance, or energy expenditure (edge weights).
The expedition team must answer one critical question:
"What is the cheapest route from our base camp (start) to the rendezvous point (end)?"
This is precisely the single-source shortest path problem, one of the most studied and widely applied problems in computer science and operations research.
- GPS Navigation — finding the fastest route between two locations.
- Network routing — forwarding data packets along minimum-latency paths.
- Supply chain optimisation — minimising logistics cost between warehouses.
- Game AI — pathfinding for NPC movement on weighted maps.
Dijkstra's algorithm was the natural first choice because:
- The expedition graph has non-negative weights (travel costs ≥ 0).
- It is greedy and optimal: the node currently closest to the source is settled first and never reconsidered.
- It is efficient:
O((V + E) log V)with a binary heap.
function DIJKSTRA(G, source, target):
dist[v] ← ∞ for all v in V
dist[source] ← 0
prev[v] ← None for all v in V
PQ ← MinHeap()
PQ.push((0, source))
while PQ is not empty:
(d, u) ← PQ.pop_min()
if u already visited: continue
mark u as visited
if u == target: break
for (v, w) in G.neighbors(u):
if dist[u] + w < dist[v]:
dist[v] ← dist[u] + w
prev[v] ← u
PQ.push((dist[v], v))
return dist[target], reconstruct_path(prev, target)
| Resource | Complexity |
|---|---|
| Time | O((V + E) log V) |
| Space | O(V + E) |
- Each of the V vertices is extracted from the heap once: O(V log V).
- Each of the E edges may cause one heap push: O(E log V).
- Total: O((V + E) log V).
| Test | Graph | Expected | Got |
|---|---|---|---|
| 1 | {0:[(1,3),(2,1)], 1:[(3,6)], 2:[(3,2)], 3:[]} |
3 | ✅ 3 |
| 2 | {0:[(1,4)], 1:[(2,1)], 2:[(3,2)], 3:[]} |
7 | ✅ 7 |
| 3 | {0:[(1,2),(2,3)], 1:[(2,4)], 2:[(3,1)], 3:[]} |
4 | ✅ 4 |
Floyd–Warshall computes all-pairs shortest paths in a single execution, which is useful when the team may later need distances between any pair of checkpoints — not just a fixed start/end. For our use case, we simply extract the start→end cell from the resulting matrix.
function FLOYD_WARSHALL(G):
dp[i][j] ← weight(i,j) if edge exists
dp[i][i] ← 0
dp[i][j] ← ∞ otherwise
for k from 0 to V−1: // intermediate node
for i from 0 to V−1: // source
for j from 0 to V−1: // destination
if dp[i][k] + dp[k][j] < dp[i][j]:
dp[i][j] ← dp[i][k] + dp[k][j]
next[i][j] ← next[i][k]
return dp, next // dp[start][end] = shortest distance
| Resource | Complexity |
|---|---|
| Time | O(V³) |
| Space | O(V²) |
| Algorithm | Time | Space | Negative Weights | All-Pairs | Path Reconstruction |
|---|---|---|---|---|---|
| Dijkstra | O((V+E) log V) | O(V+E) | ❌ No | ❌ No | ✅ Yes |
| Floyd–Warshall | O(V³) | O(V²) | ✅ Yes | ✅ Yes | ✅ Yes |
On the three required test cases (4 nodes, ≤ 4 edges), both algorithms finish in < 1 ms — too small to distinguish. Differences emerge at scale.
The main.py script generates random directed graphs and benchmarks both algorithms.
20-node graph (~136 edges):
| Algorithm | Typical Time (ms) |
|---|---|
| Dijkstra | ~0.015 |
| Floyd–Warshall | ~0.53 |
50-node graph (~562 edges):
| Algorithm | Typical Time (ms) |
|---|---|
| Dijkstra | ~0.05 |
| Floyd–Warshall | ~7.6 |
| Graph Characteristic | Best Algorithm | Reason |
|---|---|---|
| Sparse, non-negative weights | Dijkstra | Heap efficiency dominates on sparse graphs |
| Dense, non-negative | Floyd–Warshall | All-pairs amortised; O(V³) acceptable for dense |
| Need all-pairs distances | Floyd–Warshall | Single run returns full distance matrix |
| Large sparse graphs (V>10³) | Dijkstra | O((V+E) log V) scales best |
- Dijkstra uses O(V + E) — heap + predecessor map.
- Floyd–Warshall uses O(V²) — the full distance matrix. For V=1000 that's ~8 MB; for V=10000 it becomes ~800 MB — impractical.
The GUI is built with tkinter (window/widgets) and matplotlib (graph canvas), with networkx used for graph drawing helpers.
┌───────────────────────────────────┬─────────────────────────────────────┐
│ LEFT CONTROL PANEL │ MATPLOTLIB CANVAS │
│ • Graph text area (editable) │ │
│ • Start / End node fields │ Directed weighted graph drawn │
│ • Algorithm radio buttons │ with circular node layout. │
│ ○ Dijkstra │ │
│ ○ Floyd-Warshall │ Shortest path highlighted in │
│ • [Load Graph] button │ orange when an algorithm runs. │
│ • [Run Selected] button │ │
│ • [Compare Both] button │ Node colours: │
│ • [Clear] button │ 🔵 regular 🟢 start 🔴 end │
│ • Results text log │ 🟠 path node │
│ • Status bar │ Edge labels show weights. │
└───────────────────────────────────┴─────────────────────────────────────┘
| Feature | Details |
|---|---|
| Graph input | Multi-line text area pre-filled with Test Case 1; any valid Python adjacency dict is accepted |
| Load Graph | Parses input, validates format, builds Graph object, draws in the canvas |
| Run Selected | Runs the chosen algorithm (Dijkstra or Floyd-Warshall); shows distance, path, time; highlights path |
| Compare Both | Runs both algorithms side-by-side, logs results in a comparison table, highlights the best path |
| Clear | Resets canvas and results log |
| Error handling | Invalid input, missing nodes, no-path situations shown via dialog boxes or log messages |
| Dark theme | Full dark colour palette for comfortable use |
For the Expedition Planner scenario — sparse graphs with non-negative weights and a single start/end query:
Dijkstra's algorithm is the best overall choice.
Reasoning:
- The graph is sparse (V ≤ hundreds, E ≤ thousands in realistic expedition maps).
- All edge weights (distances, travel times) are non-negative by construction.
O((V + E) log V)is the most efficient single-source algorithm for this input class.- Path reconstruction is straightforward via the predecessor array.
When to use Floyd–Warshall instead:
- When the full distance table between all checkpoints is needed up-front (e.g., a planning phase before any route queries).
- When the graph is small and dense, making O(V³) acceptable and the simplicity of the triple-loop implementation advantageous.
- Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269–271.
- Floyd, R. W. (1962). Algorithm 97: Shortest path. Communications of the ACM, 5(6), 345.
- Cormen, T. H. et al. (2022). Introduction to Algorithms (4th ed.). MIT Press.