Weighted Graph Algorithms

When you navigate using a GPS, it doesn't just find a route; it finds the best route based on distance or time. When an internet router directs data packets, it must balance traffic to avoid congestion. These real-world optimization problems are solved using weighted graph algorithms, where the numerical values on edges—representing cost, distance, capacity, or time—transform an abstract network into a quantifiable model for decision-making. Mastering these algorithms is essential for tackling problems in networking, logistics, operations research, and any domain where efficient resource allocation is critical.

Graph Representations with Weights

A weighted graph is a structure consisting of vertices (or nodes) and edges, where each edge carries a numerical value, or weight. This weight quantifies the relationship it represents, such as the distance between two cities, the cost of a flight, or the bandwidth of a network link. How you store this graph in memory profoundly impacts algorithm efficiency.

The two primary representations are the adjacency matrix and the adjacency list. An adjacency matrix is a 2D array where cell matrix[i][j] stores the weight of the edge from vertex $i$ to vertex $j$. A special value (like infinity or null) indicates no edge. This representation provides $O(1)$ edge weight lookup but consumes $O(V^2)$ space, making it inefficient for sparse graphs (graphs with relatively few edges).

In contrast, the adjacency list representation uses an array of lists. Each index i in the array holds a list of pairs for each neighbor of vertex $i$, where each pair contains the neighbor's identifier and the edge weight. This is space-efficient for sparse graphs, using $O(V+E)$ space, but finding a specific edge's weight requires scanning a list, taking $O(k)$ time where $k$ is the number of neighbors. For most weighted graph algorithms, the adjacency list is the preferred representation due to its efficiency in iterating over a vertex's edges, a common operation.

Single-Source Shortest Path Algorithms

The quintessential problem is finding the shortest path from a single source vertex to all other vertices. The choice of algorithm depends heavily on the graph's properties, particularly the presence of negative edge weights.

Dijkstra's algorithm is the workhorse for graphs with non-negative weights. It operates on a greedy principle: at each step, it expands the shortest known path from the source. It maintains a set of vertices whose final shortest distance is known and a priority queue of vertices to explore. The algorithm repeatedly extracts the vertex with the minimum tentative distance from the queue, relaxes its outgoing edges, and updates distances. Its time complexity is $O((V+E)\log V)$ with a binary heap-based priority queue. Crucially, Dijkstra fails if the graph contains negative-weight edges because once a vertex is processed, it is never revisited, which could miss a better path discovered via a negative edge later.

For graphs that may contain negative-weight edges, the Bellman-Ford algorithm is used. It can detect and report the presence of a negative weight cycle—a cycle whose total weight is negative—reachable from the source, which would allow infinitely decreasing shortest paths. The algorithm works by relaxing all edges $|V|-1$ times. If a distance can still be improved on the $|V|$-th pass, a negative cycle exists. Its time complexity is $O(V\ast E)$, making it slower than Dijkstra but more versatile. It serves as the foundation for distance-vector routing protocols in networks.

Step-by-step reasoning for a shortest path problem:

1. Analyze the graph: Check for negative edge weights.
2. Choose the algorithm: Non-negative weights? Use Dijkstra. Negative weights possible? Use Bellman-Ford.
3. Execute: For Dijkstra, use a priority queue. For Bellman-Ford, iterate V-1 times over all edges.
4. Verify: For Bellman-Ford, perform an extra iteration to check for negative cycles.

Minimum Spanning Tree Algorithms

While shortest path algorithms connect one node to all others, a different problem is connecting all nodes to each other at the minimum total cost, without creating cycles. The result is a Minimum Spanning Tree (MST)—a subset of edges that connects all vertices into a tree structure with the smallest possible total edge weight. Imagine laying cable to connect a set of buildings; the MST gives you the cheapest network layout.

Kruskal's algorithm is edge-centric. It sorts all edges by weight in ascending order. Then, it iterates through the sorted list, adding the next edge to the MST if it does not create a cycle with the already selected edges. Cycle detection is efficiently performed using a Union-Find (Disjoint Set) data structure. Its complexity is dominated by sorting: $O(E\log E)$, which is effectively $O(E\log V)$.

Prim's algorithm is vertex-centric and resembles Dijkstra's algorithm. It starts from an arbitrary vertex and grows the MST one vertex at a time. At each step, it adds the cheapest edge that connects a vertex in the growing MST to a vertex outside of it. This "cheapest crossing edge" is efficiently found using a priority queue. Its time complexity is the same as Dijkstra's: $O((V+E)\log V)$ with an adjacency list and a binary heap. Both algorithms are greedy and produce an optimal MST for connected, undirected graphs.

Algorithm Selection and Application

Choosing the right algorithm is a critical skill. The decision is driven by the problem's goal and the graph's properties. Use this framework:

• Goal: Shortest Path from One Source
• Are edge weights non-negative? -> Dijkstra's Algorithm (Fast, $O((V+E)\log V)$).
• Can edges have negative weights? -> Bellman-Ford Algorithm (Slower, $O(V\ast E)$, detects negative cycles).
• Goal: Connect All Nodes at Minimum Total Cost (MST)
• Graph is dense (many edges)? -> Prim's Algorithm often performs well.
• Graph is sparse? -> Kruskal's Algorithm is simple and efficient, especially with Union-Find.
• Goal: All-Pairs Shortest Paths (A broader topic implied by network flow contexts): For this, you would use algorithms like Floyd-Warshall or repeated applications of Dijkstra/Bellman-Ford.

Understanding weight representation ties directly into selection. A dense graph stored as an adjacency list might still be processed efficiently by Prim's algorithm, while Kruskal's initial sort on a dense graph ($E\approx V^2$) becomes more costly. The core principle is that these algorithms solve diverse optimization problems by systematically exploiting the structure of weighted graphs.

Common Pitfalls

1. Using Dijkstra with Negative Weights: This is the most frequent error. Remember, Dijkstra's greedy assumption breaks if a negative edge can appear later to reduce a path cost to a vertex already "settled." Always check the problem constraints. If negative weights are a possibility, Bellman-Ford is the safe choice.
2. Inefficient Graph Representation: Using an adjacency matrix for a sparse social network graph (billions of users, but each has only hundreds of connections) is computationally and spatially disastrous. Match the representation to the graph's density: lists for sparse graphs, matrices for dense graphs or when constant-time edge lookup is paramount.
3. Misunderstanding MST vs. Shortest Path: A Minimum Spanning Tree minimizes the total cost to connect all nodes, but the path between any two nodes within the MST is not necessarily the shortest path between them in the original graph. They solve different problems. Confusing them leads to incorrect solutions for tasks like finding the shortest delivery route between two specific warehouses.
4. Ignoring Cycle Detection in Kruskal's Algorithm: Simply picking the smallest edges without checking for cycles will not yield a tree—it will create a forest with cycles. The Union-Find data structure is not just an optimization; it is essential for correct cycle detection in near-constant time.

Summary

• Weighted graphs model real-world networks by assigning numerical values (cost, distance) to edges, using adjacency lists or matrices for representation.
• Dijkstra's algorithm efficiently finds single-source shortest paths in graphs with non-negative weights, while Bellman-Ford algorithm handles graphs with negative weights and can detect negative cycles.
• Minimum Spanning Tree (MST) algorithms like Prim's (vertex-growing) and Kruskal's (edge-union with cycle checking) find the cheapest way to connect all nodes in a graph without cycles.
• Algorithm selection is critical: choose based on the problem goal (shortest path vs. MST) and graph properties (edge weight signs, density).
• Always validate graph properties—especially the absence of negative weights—before applying Dijkstra, and understand the distinct objectives of shortest-path and MST algorithms.