9.7 Weighted Graphs

You need to model relationships where connections have different costs.

algorithmsgraphsgraph-theory

9.7 Weighted Graphs

Problem

You need to model relationships where connections have different costs.

In many graph problems, not all edges are equal. A flight between two cities may take three hours while another takes ten. One network link may have high bandwidth while another is slow. One road may be short while another is long.

Treating every edge as identical loses information that is essential for finding optimal solutions.

You need a graph model that captures the cost, distance, time, capacity, risk, or value associated with each connection.

Solution

Associate a weight with every edge.

Instead of storing:

A → B

store:

A → B (5)

where 5 represents the weight.

The interpretation of the weight depends entirely on the problem domain.

Examples:

Weight Meaning Example
Distance Kilometers between cities
Time Minutes required for travel
Cost Price of a flight
Risk Probability of failure
Energy Battery consumption
Capacity Maximum throughput
Reliability Connection quality

A weighted adjacency list typically stores pairs:

graph = {
    "A": [("B", 5), ("C", 2)],
    "B": [("D", 7)],
    "C": [("D", 1)],
    "D": []
}

Each neighbor is accompanied by a weight.

Discussion

The introduction of weights changes the nature of many graph problems.

Consider:

A → B
A → C
C → D
B → D

In an unweighted graph, the shortest path is measured by edge count.

Both paths:

A → B → D

and

A → C → D

contain two edges.

They appear equally good.

Now assign weights:

A → B (10)
A → C (1)
C → D (1)
B → D (1)

Path costs become:

A → B → D = 11
A → C → D = 2

The second path is clearly better.

Once weights exist, shortest-path algorithms must optimize accumulated cost rather than edge count.

This distinction motivates algorithms such as Dijkstra, Bellman-Ford, and Floyd-Warshall.

Choosing Meaningful Weights

The weight must represent the quantity being optimized.

This sounds obvious, but many modeling mistakes begin here.

Suppose you are building a navigation system.

Possible weights include:

Weight Meaning
Distance Shortest route
Time Fastest route
Fuel Most efficient route
Toll cost Cheapest route
Accident risk Safest route

The graph structure remains identical.

Only the weight interpretation changes.

Different weights can produce completely different paths.

Always ask:

What exactly am I minimizing or maximizing?

before assigning edge weights.

Positive and Negative Weights

Many algorithms assume positive weights.

Example:

A → B (4)
B → C (3)
A → C (10)

All weights are positive.

This property allows Dijkstra's algorithm to work efficiently.

Some problems contain negative weights:

A → B (4)
B → C (-6)
A → C (5)

Negative weights often represent:

  • Credits
  • Discounts
  • Profits
  • Energy recovery
  • Gains

Negative weights require additional care.

Some algorithms remain correct.

Others become invalid.

For example:

Algorithm Negative Weights
BFS No
Dijkstra No
Bellman-Ford Yes
Floyd-Warshall Yes
A* Usually no

Whenever negative weights appear, verify algorithm assumptions carefully.

Weighted Adjacency Lists

The most common representation stores (neighbor, weight) pairs.

graph = {
    0: [(1, 5), (2, 2)],
    1: [(3, 4)],
    2: [(3, 1)],
    3: []
}

Traversal becomes:

for neighbor, weight in graph[0]:
    print(neighbor, weight)

Output:

1 5
2 2

This structure works naturally with shortest-path and spanning-tree algorithms.

Recipe: Building a Weighted Graph

Suppose the input contains:

edges = [
    ("A", "B", 5),
    ("A", "C", 2),
    ("B", "D", 7),
]

Build an adjacency list:

def build_graph(edges):
    graph = {}

    for source, target, weight in edges:
        graph.setdefault(source, []).append(
            (target, weight)
        )
        graph.setdefault(target, [])

    return graph

Result:

{
    "A": [("B", 5), ("C", 2)],
    "B": [("D", 7)],
    "C": [],
    "D": []
}

This representation supports efficient traversal and weight access.

Computing Path Costs

The cost of a path is the sum of its edge weights.

Given:

A → B (4)
B → C (3)
C → D (2)

Path:

A → B → C → D

has total cost:

4 + 3 + 2 = 9

A simple helper function:

def path_cost(path, weights):
    total = 0

    for i in range(len(path) - 1):
        total += weights[(path[i], path[i + 1])]

    return total

Example:

weights = {
    ("A", "B"): 4,
    ("B", "C"): 3,
    ("C", "D"): 2,
}

print(path_cost(
    ["A", "B", "C", "D"],
    weights
))

Output:

9

This additive property is the foundation of most shortest-path algorithms.

Weight Matrices

Some algorithms operate more naturally on matrices.

For example:

inf = float("inf")

matrix = [
    [0,   5,   2, inf],
    [inf, 0, inf,  7],
    [inf, inf, 0,  1],
    [inf, inf, inf, 0]
]

Entry:

matrix[u][v]

stores the weight of edge u → v.

Missing edges use infinity.

This representation is common in:

  • Floyd-Warshall
  • Dynamic programming approaches
  • Dense graphs
  • Matrix-based graph computations

For sparse graphs, adjacency lists are usually preferable.

Weight Types

Weights need not be integers.

Floating-point values are common.

("A", "B", 3.14)

Probabilities:

("A", "B", 0.95)

Costs:

("A", "B", 12.99)

Durations:

("A", "B", 4.5)

The algorithm usually treats weights as numeric values supporting comparison and addition.

Choose the type that matches the domain.

Recipe: Convert Unweighted to Weighted

Some algorithms expect weights even when the graph is logically unweighted.

Assign every edge a weight of one.

graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["D"],
    "D": []
}

Convert:

weighted = {
    vertex: [
        (neighbor, 1)
        for neighbor in neighbors
    ]
    for vertex, neighbors
    in graph.items()
}

Result:

{
    "A": [("B", 1), ("C", 1)],
    "B": [("D", 1)],
    "C": [("D", 1)],
    "D": []
}

Many shortest-path algorithms then operate without modification.

Weighted Trees

Weights frequently appear in trees.

Example:

      A
    /   \\n  (4)   (2)
  B       C
         / \\n       (1) (6)
       D     E

Applications include:

  • Network design
  • Routing
  • Hierarchical clustering
  • File-system metrics
  • Geographic distances

The weight of a tree path is the sum of edge weights encountered during traversal.

Many tree algorithms generalize naturally once weights are introduced.

Complexity Characteristics

Weighted graphs have the same storage complexity as their unweighted counterparts.

For adjacency lists:

Operation Complexity
Add edge O(1) amortized
Traverse neighbors O(degree)
DFS O(V + E)
BFS traversal O(V + E)
Memory usage O(V + E)

The difference is algorithmic.

Finding a shortest path in an unweighted graph often uses BFS.

Finding a shortest path in a weighted graph may require:

  • Dijkstra
  • Bellman-Ford
  • Floyd-Warshall
  • A*

The complexity depends on the algorithm, not merely the representation.

Common Pitfalls

Do not confuse edge count with path cost.

The path with fewer edges is not necessarily cheaper.

Do not use Dijkstra when negative weights are possible.

Do not choose arbitrary weights without a clear optimization objective.

Do not use floating-point equality comparisons when precision matters.

Do not store costs in integer types that may overflow.

Do not forget that weight interpretation is part of the model.

Changing the meaning of weights changes the problem being solved.

Recipe: Validate Weights

Many graph systems benefit from validating weights during graph construction.

def validate(edges):
    for source, target, weight in edges:
        if weight is None:
            raise ValueError(
                "Missing weight"
            )

Additional checks may enforce:

  • Positive weights
  • Nonnegative weights
  • Integer weights
  • Capacity constraints
  • Probability ranges

Validation catches modeling errors before algorithm execution.

Takeaway

Weighted graphs extend ordinary graph models by associating a numeric value with each edge. These weights represent quantities such as distance, time, cost, risk, energy, or capacity and fundamentally change how optimal paths are computed. Understanding weighted graph representations, path costs, positive and negative weights, and weight selection is essential because many of the most important graph algorithms are designed specifically to reason about edge weights rather than simple connectivity.