This document provides a technical comparison of the shortest-path algorithms implemented in the Expedition Planner.
| Algorithm | Strategy | Time Complexity (Worst Case) | Space Complexity | Best Use Case |
|---|---|---|---|---|
| Dijkstra | Greedy (Priority Queue) | Single-source shortest path with non-negative weights. | ||
| Floyd-Warshall | Dynamic Programming | All-pairs shortest paths or dense graphs with potential negative weights. | ||
| Brute Force | Exhaustive Search (DFS) | Finding ALL possible paths; pedagogical purposes (extremely slow). |
- Mechanism: Extracts the node with the minimum distance from a heap and relaxes its neighbors.
- Why it's efficient: It only visits each node once and each edge at most once.
- Limitation: Cannot handle negative edge weights (greedy assumption fails).
-
Complexity:
$O((V+E) \log V)$ because every vertex is extracted ($V \log V$ ) and every edge can result in a heap push ($E \log V$ ).
-
Mechanism: Iteratively considers every node
$k$ as an intermediate point between every pair$(i, j)$ . - Why it's useful: Finds paths between all pairs of nodes simultaneously. It can also detect negative cycles.
-
Limitation:
$O(V^3)$ becomes prohibitively expensive as$V$ grows beyond a few hundred. -
Complexity:
$O(V^3)$ due to the triple-nested loop over all vertices.
- Mechanism: Recursively explores every possible path from start to end without pruning.
- Why it's used here: To demonstrate the "factorial explosion" of pathfinding.
-
Limitation: In a complete graph, the number of simple paths between two nodes is
$\approx (V-2)! \times e$ . For$V=10$ , this is manageable; for$V=20$ , it's impossible. -
Complexity:
$O(V!)$ as it explores permutations of nodes.
- For Single-Source (one start to one end): Use Dijkstra.
- For Dense Graphs or All-Pairs: Use Floyd-Warshall.
- For Small Graphs or Finding All Paths: Brute Force is an option, but rarely efficient.