Concepts

This guide covers two classic families of weighted-graph problems. Shortest paths ask for the cheapest way to travel from one vertex to another. Minimum spanning trees (MSTs) ask for the cheapest set of edges that keeps every vertex connected. Both appear constantly in coding interviews and in real systems such as map routing, network protocols and cable layout.

Weighted graphs

A graph has vertices V and edges E. In a weighted graph every edge carries a number: distance, time, cost or latency. Edges may be directed (one-way streets) or undirected (two-way roads). The weight of a path is the sum of its edge weights, and a shortest path is a path of minimum total weight.

Most algorithms here work on an adjacency list: for each vertex, a list of (neighbor, weight) pairs. It uses O(V + E) memory and lets you scan the neighbors of a vertex quickly. Kruskal's algorithm instead works on a plain edge list.

n = 4
edges = [(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1)]  # (u, v, weight)

adj = [[] for _ in range(n)]
for u, v, w in edges:
    adj[u].append((v, w))
    # for an undirected graph also add: adj[v].append((u, w))

print(adj)  # [[(1, 4), (2, 1)], [(3, 1)], [(1, 2)], []]

Problem variants

• Single-source shortest paths (SSSP): distances from one source to every vertex. Dijkstra and Bellman-Ford solve this.
• Single-pair: from s to t only. In practice you run an SSSP algorithm and stop early once t is settled.
• All-pairs shortest paths (APSP): a distance for every pair. Floyd-Warshall solves this, or you run Dijkstra from every vertex.
• Minimum spanning tree: for a connected undirected graph, choose V - 1 edges that connect all vertices with the smallest total weight. Kruskal and Prim solve this.

Relaxation

Every shortest-path algorithm in this guide is built on one operation called relaxation. You keep a tentative distance dist[v] for each vertex, starting at infinity (0 for the source). Relaxing edge (u, v, w) asks: is going through u better than what we know?

from math import inf

dist = [0, inf, inf, inf]
parent = [-1, -1, -1, -1]

def relax(u, v, w):
    if dist[u] + w < dist[v]:
        dist[v] = dist[u] + w
        parent[v] = u          # remember how we reached v
        return True
    return False

relax(0, 1, 4)
relax(0, 2, 1)
relax(2, 1, 2)                 # 1 + 2 = 3 beats 4
print(dist, parent)            # [0, 3, 1, inf] [-1, 2, 0, -1]

The algorithms differ only in the order in which they relax edges. Dijkstra relaxes outgoing edges of the closest unfinished vertex first, Bellman-Ford relaxes all edges in repeated rounds, and Floyd-Warshall relaxes through each possible intermediate vertex in turn. The array forms a , and following it backwards from a target rebuilds the actual path.