# Chapter 22. Weighted Graphs

# Chapter 22. Weighted Graphs

A weighted graph is a graph in which numerical values are assigned to edges. These values are called weights. A weight may represent distance, cost, time, capacity, resistance, probability, similarity, or any other numerical quantity attached to a connection. In the most common convention, a weighted graph means an edge-weighted graph, although vertex-weighted graphs are also used in some contexts.

Weighted graphs extend ordinary graphs by adding measurement. An unweighted graph records whether two vertices are connected. A weighted graph also records how strong, expensive, long, fast, reliable, or difficult that connection is.

## 22.1 Definition

An edge-weighted graph is a graph together with a function that assigns a number to each edge.

For an undirected graph

$$
G = (V,E),
$$

a weight function is a function

$$
w : E \to \mathbb{R}.
$$

The weighted graph is the triple

$$
G = (V,E,w).
$$

For a directed graph

$$
D = (V,A),
$$

a weight function is a function

$$
w : A \to \mathbb{R}.
$$

Then the weighted directed graph is

$$
D = (V,A,w).
$$

If \(e\) is an edge or arc, the value \(w(e)\) is called the weight of \(e\).

Often the weights are nonnegative real numbers. However, some applications require negative weights, integer weights, probabilities, capacities, or symbolic values. The allowed set of weights should always be stated.

## 22.2 First Example

Let

$$
V = \{a,b,c,d\}
$$

and let the edges be

$$
E = \{\{a,b\}, \{a,c\}, \{b,d\}, \{c,d\}\}.
$$

Define the weight function by

$$
w(\{a,b\}) = 3,
$$

$$
w(\{a,c\}) = 5,
$$

$$
w(\{b,d\}) = 4,
$$

$$
w(\{c,d\}) = 1.
$$

This graph records not only which vertices are adjacent, but also a numerical value for each adjacency.

If the weights represent travel time, then the edge \(\{c,d\}\) is faster than the edge \(\{a,c\}\). If the weights represent capacity, then \(\{a,c\}\) has larger capacity than \(\{c,d\}\). The same numbers may have different meanings in different models.

## 22.3 Edge Weights and Vertex Weights

The phrase weighted graph most often refers to edge weights. In this convention, every edge has a number attached to it.

A vertex-weighted graph instead assigns numbers to vertices. Its weight function has the form

$$
w : V \to \mathbb{R}.
$$

Some graphs have both vertex weights and edge weights. For example, in a transportation network, vertices may represent stations with handling costs, while edges may represent travel times between stations.

The convention must be stated before use.

| Type | Weight function | Meaning |
|---|---|---|
| Edge-weighted graph | \(w:E\to\mathbb{R}\) | each edge has a weight |
| Vertex-weighted graph | \(w:V\to\mathbb{R}\) | each vertex has a weight |
| Mixed weighted graph | weights on \(V\) and \(E\) | both vertices and edges have weights |

In this chapter, unless otherwise stated, weighted graph means edge-weighted graph.

## 22.4 Directed Weighted Graphs

A directed weighted graph assigns a weight to each arc.

If

$$
(u,v) \in A,
$$

then

$$
w(u,v)
$$

is the weight of the arc from \(u\) to \(v\).

The reverse arc, if present, may have a different weight:

$$
w(u,v) \neq w(v,u).
$$

For example, travel time from \(u\) to \(v\) may differ from travel time from \(v\) to \(u\). A route may be uphill in one direction and downhill in the other. A network link may have asymmetric latency or bandwidth.

Thus directed weighted graphs are useful when both direction and numerical cost matter.

## 22.5 Path Weight

Let

$$
P = v_0, v_1, \ldots, v_k
$$

be a path in a weighted graph. The weight of the path is usually defined as the sum of the weights of its edges:

$$
w(P) =
\sum_{i=1}^{k} w(v_{i-1},v_i).
$$

For an undirected graph, \(w(v_{i-1},v_i)\) means the weight of the edge \(\{v_{i-1},v_i\}\). For a directed graph, it means the weight of the arc \((v_{i-1},v_i)\).

For example, suppose

$$
a \to b
$$

has weight \(2\),

$$
b \to c
$$

has weight \(7\), and

$$
c \to d
$$

has weight \(1\). Then the path

$$
a,b,c,d
$$

has total weight

$$
2 + 7 + 1 = 10.
$$

This additive convention is standard for shortest path problems, where weights often represent distance, time, or cost.

## 22.6 Shortest Paths

In an unweighted graph, the length of a path is the number of edges it uses. In a weighted graph, the length or cost of a path is usually the sum of its edge weights.

A shortest path from \(s\) to \(t\) is a path from \(s\) to \(t\) with minimum total weight among all such paths.

The shortest path need not use the fewest edges.

For example, suppose there are two paths from \(s\) to \(t\):

$$
s \to a \to t
$$

with edge weights \(1\) and \(1\), and

$$
s \to b \to c \to t
$$

with edge weights \(0.2\), \(0.2\), and \(0.2\).

The first path has two edges and total weight

$$
2.
$$

The second path has three edges and total weight

$$
0.6.
$$

Thus the second path is shorter by weight, even though it uses more edges.

This distinction is one of the main reasons weighted graphs are needed.

## 22.7 Negative Weights

Weights may be negative in some mathematical models.

A negative edge weight can represent gain, credit, energy release, profit, or a favorable transformation. However, negative weights require care.

If a graph contains a cycle whose total weight is negative, then shortest path problems may have no finite solution. By going around the negative cycle repeatedly, the path weight can be made arbitrarily small.

A directed cycle

$$
C = v_0, v_1, \ldots, v_{k-1}, v_0
$$

has weight

$$
w(C) =
\sum_{i=1}^{k} w(v_{i-1},v_i),
$$

with indices taken modulo \(k\).

If

$$
w(C) < 0,
$$

then \(C\) is called a negative cycle.

Shortest path algorithms must specify whether negative weights are allowed. Dijkstra's algorithm assumes nonnegative edge weights. Bellman-Ford can handle negative weights, but it detects negative cycles reachable from the source.

## 22.8 Capacity Weights

Not all weights are costs to be minimized.

In a flow network, an edge weight may represent capacity. A capacity tells how much flow an edge can carry.

If an arc

$$
u \to v
$$

has capacity

$$
c(u,v),
$$

then the amount of flow sent along that arc must usually satisfy

$$
0 \leq f(u,v) \leq c(u,v).
$$

Here larger weights are better, not worse.

This illustrates a general rule: a weight has no meaning by itself. Its meaning comes from the model. A distance weight, a cost weight, a capacity weight, and a probability weight obey different interpretations.

## 22.9 Similarity and Distance

Weights may represent either similarity or distance.

A distance weight is small when two vertices are close. A similarity weight is large when two vertices are close in meaning, behavior, or relation.

For example, in a document graph:

| Weight meaning | Interpretation |
|---|---|
| Distance | smaller means more similar |
| Similarity | larger means more similar |

This distinction affects algorithms. Shortest path algorithms use small weights as favorable. Clustering algorithms based on similarity may prefer large weights.

Sometimes one converts similarity into distance. If similarity lies in the interval \((0,1]\), one common transformation is

$$
d(u,v) = -\log s(u,v).
$$

This turns multiplication of similarities along paths into addition of distances.

## 22.10 Weighted Adjacency Matrix

A weighted graph can be represented by a weighted adjacency matrix.

Let

$$
V = \{v_1,\ldots,v_n\}.
$$

The weighted adjacency matrix \(M\) is defined by

$$
M_{ij} =
\begin{cases}
w(v_i,v_j), & \text{if } v_i \to v_j \text{ is an arc}, \\
0, & \text{otherwise},
\end{cases}
$$

or by another special value when no edge is present.

For shortest path problems, it is often more convenient to write

$$
M_{ij} =
\begin{cases}
w(v_i,v_j), & \text{if } v_i \to v_j \text{ is an arc}, \\
\infty, & \text{otherwise}.
\end{cases}
$$

The choice between \(0\) and \(\infty\) depends on the operation being performed. For algebraic graph theory, zero often means no edge. For shortest path algorithms, infinity often means no direct connection.

In an undirected weighted graph, the matrix is symmetric when the weight of \(\{v_i,v_j\}\) is written in both positions:

$$
M_{ij} = M_{ji}.
$$

In a directed weighted graph, symmetry is not expected.

## 22.11 Weighted Adjacency Lists

A weighted adjacency list stores, for each vertex, its neighbors together with edge weights.

For example, the directed weighted graph

$$
a \to b \quad (3),
$$

$$
a \to c \quad (5),
$$

$$
b \to d \quad (2)
$$

may be stored as

$$
a : (b,3), (c,5),
$$

$$
b : (d,2),
$$

$$
c : ,
$$

$$
d : .
$$

Adjacency lists are usually preferred for sparse graphs. They store only existing edges. Weighted adjacency matrices are more convenient for dense graphs or for algorithms that require constant-time edge lookup.

## 22.12 Edge Lists

A weighted edge list stores each edge together with its weight.

For an undirected graph, the list may contain triples

$$
(u,v,w).
$$

For a directed graph, the same triple represents an arc from \(u\) to \(v\) with weight \(w\).

For example,

$$
(a,b,3),
\qquad
(a,c,5),
\qquad
(b,d,2)
$$

is a weighted edge list.

Edge lists are useful for algorithms that process edges directly. Kruskal's minimum spanning tree algorithm, for example, sorts edges by weight.

## 22.13 Minimum Spanning Trees

In a connected undirected weighted graph, a spanning tree is a tree that includes every vertex. A minimum spanning tree is a spanning tree whose total edge weight is as small as possible.

The weight of a subgraph is usually the sum of its edge weights:

$$
w(H) =
\sum_{e \in E(H)} w(e).
$$

Minimum spanning trees are used when one wants to connect all vertices while minimizing total cost.

Typical applications include:

| Application | Vertices | Edge weights |
|---|---|---|
| Network design | sites | construction cost |
| Clustering | data points | dissimilarity |
| Circuit layout | terminals | wiring length |
| Road planning | locations | building cost |

The two classical algorithms are Kruskal's algorithm and Prim's algorithm.

## 22.14 Shortest Path Trees

A shortest path tree is different from a minimum spanning tree.

Given a source vertex \(s\), a shortest path tree contains shortest paths from \(s\) to the reachable vertices.

It minimizes distance from one source to each vertex. It does not necessarily minimize total edge weight of the tree.

A minimum spanning tree minimizes total connection cost across all vertices. It does not necessarily preserve shortest paths from a source.

These two structures answer different questions.

| Structure | Main goal |
|---|---|
| Minimum spanning tree | connect all vertices with minimum total edge weight |
| Shortest path tree | preserve shortest paths from one source |
| Minimum arborescence | directed analogue of a rooted spanning tree problem |

Confusing these objects is a common error.

## 22.15 Weighted Degree

In an unweighted graph, the degree of a vertex counts incident edges. In a weighted graph, one may also define weighted degree.

For an undirected weighted graph, the weighted degree of a vertex \(v\) is

$$
\deg_w(v) =
\sum_{e \text{ incident with } v} w(e).
$$

For a directed weighted graph, one may define weighted out-degree and weighted in-degree:

$$
\deg_w^+(v) =
\sum_{(v,u)\in A} w(v,u),
$$

$$
\deg_w^-(v) =
\sum_{(u,v)\in A} w(u,v).
$$

These quantities are useful when weights represent flow, traffic, strength, or interaction frequency.

If weights represent costs, weighted degree may have a less direct interpretation. Again, meaning depends on the model.

## 22.16 Weighted Graphs and Metrics

A weighted graph can define a metric on its vertices if the weights are nonnegative and distances are taken to be shortest path distances.

Define

$$
d(u,v)
$$

as the minimum total weight of a path from \(u\) to \(v\).

For an undirected connected graph with nonnegative edge weights, this distance satisfies:

| Property | Statement |
|---|---|
| Nonnegativity | \(d(u,v) \geq 0\) |
| Symmetry | \(d(u,v)=d(v,u)\) |
| Triangle inequality | \(d(u,w)\leq d(u,v)+d(v,w)\) |

If zero-weight edges connect distinct vertices, then \(d(u,v)=0\) may occur with \(u\neq v\), so the function is a pseudometric rather than a metric.

For directed graphs, shortest path distance is generally asymmetric.

## 22.17 Applications

Weighted graphs appear whenever connections carry quantitative information.

| Application | Vertices | Edges | Weight |
|---|---|---|---|
| Road network | intersections | roads | distance or travel time |
| Computer network | routers | links | latency or bandwidth |
| Airline network | airports | routes | price or flight time |
| Social graph | people | interactions | interaction strength |
| Citation graph | papers | citations | influence score |
| Knowledge graph | entities | relations | confidence |
| Image graph | pixels or regions | adjacency | similarity |
| Electrical network | junctions | wires | resistance |
| Flow network | locations | channels | capacity |
| Machine learning | data points | similarity edges | distance or affinity |

The same abstract structure supports many interpretations. The graph gives topology. The weights give measurement.

## 22.18 Common Mistakes

A common mistake is to assume that every weighted problem is a shortest path problem. Some weights represent capacity, similarity, reliability, or probability, where maximizing or multiplying may be more appropriate than minimizing sums.

Another mistake is to treat missing edges as weight zero. In shortest path problems, a missing edge should usually behave like infinite cost, not zero cost.

A third mistake is to confuse shortest path trees with minimum spanning trees. One preserves shortest distances from a source. The other minimizes total connection cost.

A fourth mistake is to ignore whether negative weights are allowed. Algorithms that work for nonnegative weights may fail when negative weights occur.

## 22.19 Summary

A weighted graph is a graph together with a weight function on its edges or arcs. In the usual edge-weighted case,

$$
w:E\to\mathbb{R}
$$

or

$$
w:A\to\mathbb{R}.
$$

Weights add quantitative meaning to graph structure. They may represent cost, distance, time, capacity, resistance, similarity, probability, or strength.

Weighted graphs support shortest path problems, minimum spanning trees, flow networks, clustering, network design, routing, and many other models. Their correct use depends on interpreting weights carefully and choosing algorithms that match that interpretation.