Weighted Graph Basics and Applications
Learn what weighted graphs are, how edge weights are stored, and when to use them. Explore common algorithms for weighted graphs including Dijkstra, Prim, and Kruskal.
Detailed Explanation
Weighted Graphs
A weighted graph assigns a numeric value (weight) to each edge. This weight can represent distance, cost, time, capacity, or any other metric. Weighted graphs unlock a set of algorithms that are not meaningful on unweighted graphs.
Representation
Weights are stored alongside edges in the adjacency structure:
Adjacency List:
A: [(B, 4), (C, 2)]
B: [(D, 3)]
C: [(B, 1), (D, 5)]
Adjacency Matrix:
A B C D
A 0 4 2 ∞
B ∞ 0 ∞ 3
C ∞ 1 0 5
D ∞ ∞ ∞ 0
Common Algorithms for Weighted Graphs
- Dijkstra's algorithm — Shortest path from one source (non-negative weights)
- Bellman-Ford — Shortest path with negative weights
- Prim's algorithm — Minimum spanning tree (greedy, grows one tree)
- Kruskal's algorithm — Minimum spanning tree (sorts edges, uses union-find)
- Floyd-Warshall — All-pairs shortest paths
Negative Weights
Negative edge weights are valid in many contexts (e.g., representing profit), but they complicate shortest-path algorithms. Dijkstra does not work with negative weights; Bellman-Ford handles them but is slower. Negative cycles make shortest paths undefined because you can loop forever to decrease the distance.
Unweighted as a Special Case
An unweighted graph can be viewed as a weighted graph where all edges have weight 1. BFS on an unweighted graph is equivalent to Dijkstra on a graph with unit weights.
Use Case
Weighted graphs model real-world networks where connections have associated costs. Road networks use weights for distance or travel time. Airline route planners use weights for ticket prices or flight durations. Telecommunication networks use weights for bandwidth or latency. Supply chain logistics uses weights for shipping costs between distribution centers.