7.2 Paths, Connectivity, Trees, and Shortest Paths: Different Weights Require Different Algorithms

In navigation, "shortest" may refer to distance, time, cost, or number of transfers. Before selecting an algorithm, you must first determine how path costs accumulate, whether edge weights can be negative, whether the graph is directed, and whether a single source node or all pairs of nodes are required.

Walk, Trail, Path, and Cycle

Terminology varies slightly across textbooks, but in this lesson we use the following definitions:

• Walk: A sequence of adjacent vertices connected by edges, allowing vertices and edges to be reused;
• Trail: A sequence with no repeated edges;
• Path (simple path): A sequence with no repeated vertices;
• Cycle: A closed trail with no repeated vertices except the common start and end; in an undirected simple graph it has at least 3 edges.

In algorithms, a general vertex sequence is often informally referred to as a path. When proving properties, it's important to explicitly state whether vertex or edge repetition is allowed.

In unweighted graphs, the length of a path typically refers to the number of edges. In weighted graphs, the path weight is the sum of the edge weights along the path.

Connected Components

In an undirected graph, if there is a path between any two vertices, the graph is connected. Reachability including zero-length paths forms an equivalence relation, and the equivalence classes are the connected components.

In directed graphs, we distinguish between:

• Strongly connected: For any u,v, each can reach the other;
• Weakly connected: The graph remains connected when edge directions are ignored.

One-way reachability does not imply strong connectivity. For example, if service A calls service B, it does not require that B can call A.

Equivalent Characterizations of Trees

For a finite undirected simple graph with at least one vertex, each condition below is equivalent to being a tree:

• It is connected and has no cycles;
• Between any two vertices, there is exactly one simple path;
• It is connected and has |V|-1 edges;
• It has no cycles and has |V|-1 edges;
• It is connected, and removing any edge disconnects it;
• It is acyclic, and adding any new edge between nonadjacent vertices creates exactly one cycle.

These equivalent properties allow proofs to choose the most convenient entry point.

The last two prerequisites matter: every edge in a forest is a bridge, yet the forest may be disconnected; an already cyclic graph cannot be proved to be a tree merely because adding edges creates cycles. A single vertex with no edges is a tree.

Once a root is specified, a tree defines parent-child relationships, depth, and subtree structure. An unrooted tree has no inherent "above" or direction. File systems are often modeled as rooted trees, but hard links, symbolic links, and mounts can break the simple tree model.

Spanning Trees and Minimum Spanning Trees

A spanning tree of a connected undirected graph includes all vertices and selects exactly |V|-1 edges to maintain connectivity.

For a weighted graph, a minimum spanning tree (MST) minimizes the total edge weight. It optimizes the "total cost of connecting all vertices," not the shortest path between any two points.

Kruskal

1. Sort all edges by weight in ascending order;
2. Add edges one by one if they don’t form a cycle;
3. Use a union-find data structure to track connected components.

Prim

1. Start with a single vertex and maintain a growing tree;
2. At each step, add the edge with the smallest weight that connects the current tree to an unvisited vertex;
3. Use a priority queue to manage candidate edges.

The cut property concerns the edges already chosen. If they extend to an MST and a cut crosses none of them, adding any lightest crossing edge preserves that extendability. Equal weights may yield several MSTs with the same total weight; a lightest edge need not belong to every MST.

MSTs are typically applied to undirected graphs. For network cabling scenarios requiring directionality, reliability redundancy, or capacity constraints, a standard MST model may be insufficient.

For a triangle with AB=2,AC=2,BC=1, an MST can select AB,BC with total weight 3. Its A-to-C path costs 3, although the direct AC edge costs 2. Negative weights do not invalidate the MST cut property; disconnected graphs call for a minimum spanning forest.

Unweighted Shortest Path: BFS

When all edge costs are equal and nonnegative, BFS visits nodes in edge-count layers:

Layer 0: source node
Layer 1: nodes reachable in one edge
Layer 2: nodes reachable in two edges
...

The first time a node is encountered, any shorter path must have been discovered in an earlier layer, ensuring the path with the fewest edges is found.

When edge weights are 0 or 1, a 0-1 BFS using a double-ended queue is appropriate; a standard FIFO BFS is no longer sufficient.

Non-negative Weight Shortest Path: Dijkstra

Dijkstra maintains tentative distances:

dist[s] = 0
all other dist = ∞

Each iteration extracts the vertex with the smallest tentative distance from the priority queue, then relaxes its outgoing edges:

if dist[v] + w(v,u) < dist[u]:
    dist[u] = dist[v] + w(v,u)
    parent[u] = v

The correctness of this algorithm relies on non-negative edge weights: when a vertex's tentative distance is finalized, no path going through unprocessed vertices can reduce its distance further.

Negative edges invalidate permanent greedy finalization. A version that repeatedly reopens processed vertices can still obtain correct results without negative cycles as a label-correcting algorithm, but it loses the standard Dijkstra polynomial-time guarantee. The implementation below explicitly rejects negative weights.

For S→A:2,S→B:5,B→A:−4, a version that finalizes A at distance 2 and never revises it misses the actual distance 1. Returning immediately when target A is popped fails for the same reason.

A common time complexity when using an adjacency list with a binary heap:

O((V + E) log V)

This depends on the priority queue implementation and whether it supports decrease-key operations. Common engineering implementations re-enqueue nodes and skip outdated entries during extraction.

This Python 3 example assumes nonnegative integer weights, string vertices, a finite static graph containing every neighbor key, and an existing source. It returns distances; record predecessors on successful relaxations if paths are required:

from heapq import heappush, heappop
from math import inf

def dijkstra(graph, source):
    if any(weight < 0 for edges in graph.values() for _, weight in edges):
        raise ValueError("nonnegative weights required")
    distance = {v: inf for v in graph}
    distance[source] = 0
    heap = [(0, source)]
    while heap:
        cost, v = heappop(heap)
        if cost != distance[v]:
            continue  # An improved entry has superseded this one.
        for u, weight in graph[v]:
            candidate = cost + weight
            if candidate < distance[u]:
                distance[u] = candidate
                heappush(heap, (candidate, u))
    return distance

graph = {"S": [("A", 10), ("B", 1)], "A": [],
         "B": [("A", 1), ("C", 0)], "C": [], "U": []}
result = dijkstra(graph, "S")
print(result["A"], result["C"], result["U"])  # 2 1 inf

A is first queued at distance 10, then improved to 2; the stale entry is skipped. Zero-weight edges are valid and U is unreachable. Duplicate heap entries use up to O(E) space, with a general bound O(V+E log(E+1)); for simple graphs this can be written O((V+E)log(V+1)). A decrease-key implementation instead keeps O(V) vertices in its heap.

Negative Edges and Negative Cycles: Bellman–Ford

Bellman–Ford repeatedly relaxes all edges, enabling it to handle edges with negative weights and detect negative cycles reachable from the source vertex.

A reachable negative cycle makes the shortest walk weight unbounded below for targets on the cycle or reachable from it. Other targets can still have finite distances. For S→A:1,A→B:−2,B→A:0,S→T:5, A and B are affected while T still has distance 5. Requiring vertex-simple paths instead defines a different optimization problem.

Typical complexity:

O(VE)

Slower than Dijkstra, but with different modeling assumptions. Choosing an algorithm should not be based solely on performance metrics, consider the assumptions about edge weights as well.

DAG Shortest Path

Vertices in a directed acyclic graph (DAG) can be processed in topological order, and each edge needs to be relaxed only once:

O(V + E)

A DAG cannot contain negative cycles, even with negative edges, so the algorithm remains valid. This model is well-suited for problems involving task costs and pipeline critical paths.

For the longest critical path, replace minimization with maximization and specify whether task durations belong to vertices or edges; shortest-path output is not automatically project duration.

All-Pairs and Multi-Objective Cost

If you need shortest paths between all pairs of nodes, consider either Floyd–Warshall O(V³) or running multiple single-source algorithms. The choice depends on graph density, presence of negative edges, and overall scale.

Real-world navigation often involves multiple objectives: time, cost, risk. Adding these into a single weighted metric requires business-defined, interpretable conversion factors; otherwise, seeking the Pareto frontier is more appropriate than claiming a single "optimal" solution exists.

If edge weights vary over time, static shortest paths may become invalid. Models incorporating FIFO time dependencies, waiting times, and real-time updates are necessary.

Completion Checklist

1. Prove that the tree has |V|-1 edges;
2. Manually apply Kruskal's and Prim's algorithms to the same weighted graph;
3. Construct an example with a negative edge that causes Dijkstra's algorithm to fail;
4. Use Bellman–Ford to determine whether a negative cycle is reachable from the source node;
5. Compute shortest paths and the longest critical path for a DAG;
6. Explain why the Minimum Spanning Tree differs from the shortest path tree rooted at the headquarters.

References

• Princeton Algorithms: Shortest Paths
• Princeton Algorithms: Minimum Spanning Trees