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 parent array forms a shortest-path tree, and following it backwards from a target rebuilds the actual path.

Negative edges and negative cycles

Negative weights are legal in Bellman-Ford and Floyd-Warshall but break Dijkstra's greedy assumption. A negative cycle is a cycle whose total weight is below zero. If one is reachable from the source, you can loop around it forever, so the shortest distance is undefined. Detecting such a cycle is a useful result in its own right, for example for spotting currency arbitrage.

Choosing an algorithm

Minimum spanning trees

A spanning tree of a connected undirected graph touches every vertex using exactly V - 1 edges and has no cycle. The MST is the spanning tree of least total weight. Two facts make greedy algorithms correct here. The cut property says that the lightest edge crossing any split of the vertices into two groups belongs to some MST. The cycle property says that the heaviest edge on any cycle can be left out. Kruskal adds edges from lightest to heaviest and skips any edge that would close a cycle, using union-find. Prim grows one tree from a start vertex, always adding the cheapest edge that leaves the tree.

An MST is not the same thing as a shortest-path tree. The MST minimizes the total length of cable; the shortest-path tree minimizes each vertex's distance to the source.

    A ---1--- B
     \       /
      3     1
       \   /
         C

MST (total 2):            A-B, B-C   -> A to C costs 2 via B
Shortest-path tree from A: A-B, B-C  (here they agree)
Change A-C to 1.5: the MST is still A-B, B-C,
but the shortest path A to C becomes the direct edge.

Summary

• Shortest paths minimize the weight from a source; MSTs minimize the total weight that keeps an undirected graph connected.
• Relaxation is the shared building block; algorithms differ in the order they relax edges.
• Pick the algorithm by edge weights (none, 0/1, non-negative, negative) and by whether you need one source or all pairs.
• Kruskal and Prim are correct because of the cut and cycle properties.