Shortest-path selection matrix, Kahn's topological sort, Disjoint Set Union (DSU), and Tarjan's SCC.
T(V, E) = O\bigl((V + E)\log V\bigr)
Requires non-negative edge weights (w(u, v) >= 0) so settled vertices never need relaxation.
0 \le h(u) \le d^*(u, t) \quad \text{and} \quad h(u) \le w(u, v) + h(v)
Admissible and consistent heuristics guarantee A* expands the minimum number of nodes.
Select the shortest-path algorithm based on edge weight constraints and query cardinality.
| Algorithm | Edge Weights | Time Complexity | Space | Best For |
|---|---|---|---|---|
| BFS | Unweighted (w = 1) | O(V + E) | O(V) | Minimum hops in unweighted graphs |
| 0-1 BFS (Deque) | w in {0, 1} | O(V + E) | O(V) | Grid mazes with free/cost-1 edges |
| Dijkstra (Min-Heap) | w >= 0 | O((V + E) log V) | O(V) | Single-source non-negative road/network graphs |
| Bellman-Ford | Any real w (detects neg cycles) | O(V * E) | O(V) | Arbitrage detection & K-stop constrained paths |
| Floyd-Warshall | Any real w (no neg cycles) | O(V^3) | O(V^2) | All-pairs shortest paths on dense graphs (V <= 400) |
import heapq
def dijkstra(n: int, adj: list[list[tuple[int, int]]], src: int) -> list[ float]:
dist = [float('inf')] * n
dist[src] = 0.0
pq: list[tuple[float, int]] = [(0.0, src)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue # Skip stale heap entry
for v, weight in adj[u]:
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
heapq.heappush(pq, (dist[v], v))
return dist
class UnionFind:
def __init__(self, n: int) -> None:
self.parent = list(range(n))
self.size = [1] * n
def find(self, x: int) -> int:
while x != self.parent[x]:
self.parent[x] = self.parent[self.parent[x]]
x = self.parent[x]
return xFor a directed graph, use Kahn's in-degree topological sort (if processed count < V, a cycle exists) or 3-color DFS (White/Gray/Black). For an undirected graph, use Union-Find or parent-tracked DFS.