Released · improving
Algorithm
Find shortest paths with Dijkstra, Bellman-Ford and Floyd-Warshall, and build minimum spanning trees with Kruskal and Prim.
A shortest-path problem asks for the path of least total weight between vertices of a weighted graph. A minimum spanning tree (MST) is the cheapest set of edges that connects every vertex of an undirected graph without forming a cycle. The core algorithms of this topic are Dijkstra, Bellman-Ford, Floyd-Warshall, 0-1 BFS, Kruskal and Prim.
These algorithms run inside map navigation, network routing protocols such as OSPF and RIP, game path finding, cable and pipe layout, and clustering. They are also interview staples, because they test whether you can model a problem as a graph and pick the algorithm that fits the weights: negative or not, only 0 and 1, sparse or dense.
Get comfortable with BFS and priority queues (heaps) first. Then learn relaxation, the operation every shortest-path algorithm shares, and trace Dijkstra by hand on a small graph. Next, see why negative edges call for Bellman-Ford, implement Kruskal with union-find, and finish with practice problems that run Dijkstra on an expanded state graph.
Every shortest-path algorithm is built on relaxation, checking whether going through u gives a shorter route to v. The algorithms differ only in the order they relax edges.
With non-negative weights, a binary heap pops and settles the closest vertex each time, giving all single-source distances in O((V + E) log V).
Bellman-Ford accepts negative edges and detects negative cycles; Floyd-Warshall computes the distance between every pair of vertices in O(V^3).
Kruskal adds edges from lightest to heaviest and uses union-find to avoid cycles; Prim grows one tree by its cheapest outgoing edge. The cut property makes both correct.
heapq pops (distance, vertex) pairs in order of distance, and a popped pair whose distance is larger than the recorded one is stale and skipped. When a neighbor's distance improves, the code updates it and pushes a new pair. Running python dijkstra.py prints the shortest distances from A: {'A': 0, 'B': 3, 'C': 1, 'D': 4}.
dijkstra.py
import heapq
def dijkstra(graph, source):
dist = {source: 0}
heap = [(0, source)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue # stale entry
for v, w in graph[u]:
nd = d + w
if nd < dist.get(v, float("inf")):
dist[v] = nd
heapq.heappush(heap, (nd, v))
return dist
graph = {
"A": [("B", 4), ("C", 1)],
"B": [("D", 1)],
"C": [("B", 2), ("D", 5)],
"D": [],
}
print(dijkstra(graph, "A")) # {'A': 0, 'B': 3, 'C': 1, 'D': 4}
python dijkstra.pySix chapters that take you from installation to the core ideas of Shortest paths & minimum spanning trees.
Ask questions, share experience and trade opinions about Shortest paths & minimum spanning trees.
No discussions yet. Start the first one.
0 comments
Sign in · Sign in to leave a comment.
Be the first to comment.