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

There are multiple routes from Variable Village to the Secure Stronghold, and the concept of "shortest path" defined by distance, time, cost, or transfer count can differ significantly.

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 (walk): A sequence of adjacent vertices connected by edges, allowing vertices and edges to be reused;
• Trail (trail): A sequence with no repeated edges;
• Path (simple path): A sequence with no repeated vertices;
• Cycle (cycle): A closed sequence where the starting and ending vertices are the same, and all internal vertices are distinct.

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 forms an equivalence relation, and the equivalence classes are the connected components.

In directed graphs, we distinguish between:

• Strongly connected: Any u,v can reach any other node;
• 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

A finite undirected graph is a tree if and only if the following properties are equivalent:

• 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;
• Removing any edge disconnects the graph;
• Adding any new edge creates exactly one cycle.

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

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.

Both algorithms are correct due to the cut property: the lightest edge crossing a given cut is a safe choice under appropriate conditions. When edge weights are equal, multiple distinct MSTs may exist with the same total weight.

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.

Unweighted Shortest Path: BFS

When all edge costs are equal, BFS visits nodes in distance 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.

With negative edges, this greedy reasoning breaks down. Even if certain implementations occasionally produce correct results, there is no general guarantee of correctness.

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.

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.

If a reachable negative cycle exists, traversing the cycle repeatedly can continuously decrease the path weight, meaning no finite shortest path solution exists.

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.

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

• MIT OpenCourseWare: Introduction to Algorithms