Weighted Graph — Definition, Formula & Example
A weighted graph is a graph in which every edge carries a number, called its weight. The weight usually stands for a distance, cost, or travel time between the two vertices that the edge joins.
A weighted graph is a triple , where is a graph and is a weight function that assigns a real number to each edge . The weight of a path is the sum of the weights of its edges. The graph may be undirected or directed. Many shortest-path algorithms, such as Dijkstra's algorithm, require every weight to be nonnegative.
Key Formula
Where:
- = A path made of the edges
- = The weight of the -th edge on the path
- = The number of edges in the path
- = The total weight, or length, of the path
Worked Example
Problem: Four towns A, B, C, D are joined by roads. The lengths in miles are: A–B = 10, A–C = 4, C–B = 3, B–D = 2, C–D = 12. Find the shortest route from A to D.
Step 1: Add the edge weights along the two routes that pass through only one other town.
Step 2: Add the edge weights along the two routes that pass through both B and C.
Step 3: These four routes are all the paths from A to D that do not repeat a town. Compare their totals and pick the smallest.
Answer: The shortest route is A–C–B–D, with a length of 9 miles. It uses 3 roads, one more than the route A–B–D (12 miles). The shortest route still wins because its total weight is smaller.
Why It Matters
GPS apps, airline route planners, and internet routers model their networks as weighted graphs and run shortest-path algorithms such as Dijkstra's. In a discrete math or algorithms course, weighted graphs are the setting for minimum spanning trees and the traveling salesperson problem.
Common Mistakes
Mistake: Assuming the path with the fewest edges is the shortest path.
Correction: In a weighted graph, length means total weight, not edge count. In the example, A–B–D uses only 2 roads but totals 12 miles, while A–C–B–D uses 3 roads and totals 9 miles. Always add the weights.
