Mathwords logoMathwords

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 G=(V,E,w)G = (V, E, w), where (V,E)(V, E) is a graph and w:E→Rw: E \to \mathbb{R} is a weight function that assigns a real number w(e)w(e) to each edge ee. 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

w(P)=∑i=1kw(ei)w(P) = \sum_{i=1}^{k} w(e_i)
Where:
  • PP = A path made of the edges e1,e2,…,eke_1, e_2, \ldots, e_k
  • w(ei)w(e_i) = The weight of the ii-th edge on the path
  • kk = The number of edges in the path
  • w(P)w(P) = 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.
w(A–B–D)=10+2=12,w(A–C–D)=4+12=16w(A\text{–}B\text{–}D) = 10 + 2 = 12, \qquad w(A\text{–}C\text{–}D) = 4 + 12 = 16
Step 2: Add the edge weights along the two routes that pass through both B and C.
w(A–C–B–D)=4+3+2=9,w(A–B–C–D)=10+3+12=25w(A\text{–}C\text{–}B\text{–}D) = 4 + 3 + 2 = 9, \qquad w(A\text{–}B\text{–}C\text{–}D) = 10 + 3 + 12 = 25
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.
min⁡(12, 16, 9, 25)=9\min(12,\ 16,\ 9,\ 25) = 9
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.

Related Terms

  • Graph — The kind of graph whose edges get numbers
  • Minimum Spanning Tree — Connects all vertices of a weighted graph with the smallest total weight
  • Nearest Neighbor Algorithm — Visits the closest unvisited vertex next
  • Acyclic Graph — Graph with no cycles, such as a tree
  • Bipartite Graph — Weighted bipartite graphs model job assignment and matching problems
  • Pseudograph — Permits parallel edges, which can carry different weights
  • Vertices — Points that weighted edges connect in the graph