The Central Idea
In an ordinary graph, an edge answers a basic question:
Is there a connection?
In a weighted graph, an edge may also answer:
How much, how far, how long, how costly, or how strong is that connection?
We attach a number called a weight to each edge.
What Is an Edge Weight?
Let \(e\) be an edge. A weight function assigns a numerical value to that edge.
\[ \boxed{w:E\to\mathbb{R}} \]If
\[ w(e)=7, \]then edge \(e\) has weight \(7\).
The number has meaning only through the model: it might mean \(7\) miles, \(7\) minutes, \(7\) dollars, or something entirely different.
A First Weighted Graph
Suppose
\[ V=\{A,B,C,D\} \]and the undirected edges are
\[ E= \bigl\{ \{A,B\},\{A,C\},\{B,C\},\{C,D\} \bigr\}. \]Assign weights
\[ w(A,B)=4,\qquad w(A,C)=7,\qquad w(B,C)=2,\qquad w(C,D)=5. \]The graph now records both the connection structure and a numerical value on every connection.
A Weighted Graph as a Picture
We usually display each edge weight near its edge.
Weights Do Not Change Adjacency
A weight adds information to an edge, but it does not create a new adjacency relationship.
If \(A\) and \(B\) are joined by an edge of weight \(4\), they are adjacent. The number \(4\) describes the edge; it does not create four edges.
Thus,
\[ \boxed{\text{one weighted edge is still one edge}}. \]Weights Need Units
A weight should be interpreted together with its units whenever the underlying quantity has units.
For example,
\[ w(A,B)=12 \]is incomplete as a practical statement if the value might mean \(12\) kilometers, \(12\) minutes, or \(12\) dollars.
Good models state what each weight measures.
Common Meanings of Weights
Edge weights can represent many kinds of quantities.
- distance between locations;
- travel time;
- monetary cost;
- shipping expense;
- energy required;
- risk or penalty;
- similarity or strength;
- capacity of a connection;
- probability or reliability score;
- number of interactions.
The Meaning of “Better” Depends on the Weight
Smaller weights are not always better, and larger weights are not always better.
If a weight measures cost or travel time, smaller values may be preferred. If a weight measures capacity or reliability, larger values may be preferred.
Always interpret the numerical value before optimizing anything.
Weighted Undirected Graphs
An undirected weighted edge can be written as
\[ \{u,v\} \]together with a weight
\[ w(u,v). \]Because the edge is undirected,
\[ \boxed{w(u,v)=w(v,u)} \]when both expressions refer to the same undirected edge.
Weighted Directed Graphs
Directed graphs can also carry weights.
A directed edge
\[ (u,v) \]may have weight
\[ w(u,v). \]If the reverse edge also exists, its weight may be different:
\[ \boxed{w(u,v)\text{ need not equal }w(v,u)}. \]Example: Asymmetric Travel Times
Suppose a road network contains both
\[ A\to B \]and
\[ B\to A. \]Traffic conditions or road design may give
\[ w(A,B)=8\text{ minutes} \]and
\[ w(B,A)=11\text{ minutes}. \]Direction and weight together capture information that an unweighted undirected graph would lose.
Path Weight
When a path uses several edges, a common convention is to define the weight of the path as the sum of its edge weights.
If a path uses edges \(e_1,e_2,\ldots,e_k\), then
\[ \boxed{w(P)=\sum_{i=1}^{k}w(e_i)}. \]Example: Adding Edge Weights
Suppose a path from \(A\) to \(D\) travels
\[ A\to B\to C\to D \]with edge weights
\[ 4,\qquad2,\qquad5. \]Then the path weight is
\[ \boxed{4+2+5=11}. \]Path Length and Path Weight Are Different
The length of a path often means the number of edges in the path.
The weight of a path is the combined value of those edges.
A path containing three edges can therefore have
\[ \text{length}=3 \]while its total weight might be
\[ 11. \]Fewer Edges Need Not Mean Lower Weight
Consider two routes from \(A\) to \(D\).
Route 1 uses two edges with weights \(9\) and \(8\):
\[ 9+8=17. \]Route 2 uses three edges with weights \(3\), \(4\), and \(2\):
\[ 3+4+2=9. \]Route 2 uses more edges but has the smaller total weight.
Weighted Adjacency Lists
An adjacency list can record both a neighboring vertex and the associated edge weight.
For the weighted undirected graph
\[ w(A,B)=4,\quad w(A,C)=7,\quad w(B,C)=2,\quad w(C,D)=5, \]a weighted adjacency list is
- \(A:\ (B,4),(C,7)\)
- \(B:\ (A,4),(C,2)\)
- \(C:\ (A,7),(B,2),(D,5)\)
- \(D:\ (C,5)\)
Weighted Adjacency Matrices
A weighted graph can also be stored in a matrix.
One common convention is
\[ W_{ij}= \begin{cases} w(v_i,v_j),&\text{if an edge exists},\\ 0,&\text{if no edge exists}. \end{cases} \]This convention is convenient only when an actual edge weight of \(0\) is not being used.
Example: Weighted Matrix
Using vertex order \(A,B,C,D\), the running graph can be represented as
\[ W= \begin{pmatrix} 0&4&7&0\\ 4&0&2&0\\ 7&2&0&5\\ 0&0&5&0 \end{pmatrix}. \]Since the graph is undirected, the matrix is symmetric.
When Zero Is a Valid Weight
Sometimes an edge may legitimately have weight \(0\).
In that situation, using \(0\) to mean “no edge” becomes ambiguous.
A model may instead use another symbol such as
\[ \infty \]or leave the entry blank to indicate that no connection exists.
Using Infinity for Missing Connections
When weights represent costs or distances, a common computational convention is
\[ W_{ij}= \begin{cases} w(v_i,v_j),&\text{if an edge exists},\\ \infty,&\text{if no edge exists}. \end{cases} \]The symbol \(\infty\) here does not mean that a literal infinite edge is present. It marks the absence of a usable direct connection.
Weighted Directed Matrices
In a directed weighted graph, row \(i\), column \(j\) records the weight of the edge
\[ v_i\to v_j. \]Because the reverse edge may be absent or may have another weight, the matrix need not be symmetric.
Example: Directed Weighted Matrix
Suppose
\[ w(A,B)=3,\qquad w(B,A)=8,\qquad w(B,C)=4. \]Using \(0\) to represent no edge and vertex order \(A,B,C\),
\[ W= \begin{pmatrix} 0&3&0\\ 8&0&4\\ 0&0&0 \end{pmatrix}. \]The entries \(3\) and \(8\) show that opposite directions can have different weights.
Weights as Costs
Suppose each edge weight represents a cost in dollars.
If a route uses edges with weights
\[ 12,\qquad7,\qquad5, \]then the total route cost is
\[ \boxed{\$24}. \]This additive interpretation is common in transportation, logistics, and scheduling models.
Weights as Distance
If edge weights measure distance, then the total distance of a route can be found by adding the distances of the edges used.
For example,
\[ 6.2+4.1+3.7=14.0. \]If the units are kilometers, the route distance is
\[ \boxed{14.0\text{ km}}. \]Weights as Time
A network may attach estimated travel times to edges.
A route with edge times
\[ 5,\qquad9,\qquad4 \]has total modeled travel time
\[ \boxed{18\text{ minutes}}. \]Real systems may update such weights as conditions change.
Weights as Capacity
Some weights describe how much can pass through an edge rather than a cost of using it.
A network link might have capacity
\[ 20 \]units per hour.
Capacity weights require different reasoning from additive distance or cost weights. Later network-flow lessons will develop those rules.
Weights as Strength or Similarity
In some networks, a larger weight means a stronger relationship.
For example, an edge weight might count the number of communications between two vertices or measure a similarity score.
In such a model, a larger number may indicate a closer connection rather than a more expensive one.
Not Every Weight Should Be Added
Addition is natural for quantities such as distance, time, and cost along a route.
Other quantities may require different rules. Capacity, probability, reliability, and similarity may not combine by simple addition.
The combination rule must follow the meaning of the weight.
Positive Weights
Many introductory weighted-graph problems use positive edge weights:
\[ w(e)>0. \]Positive weights naturally model distances, ordinary costs, and elapsed times.
They also avoid several complications that arise in more advanced optimization problems.
Zero Weights
Some models permit
\[ w(e)=0. \]A zero-weight edge is still an edge. It may represent a connection with no additional cost, delay, or penalty.
This is why representation conventions must distinguish zero-weight edges from missing edges when necessary.
Negative Weights
Some mathematical models allow
\[ w(e)<0. \]A negative weight might represent a credit, gain, reduction, or other signed quantity.
Negative weights require care because some shortest-path methods assume that all edge weights are nonnegative.
The relevant algorithms will be introduced later.
Parallel Edges with Different Weights
In graph types that permit multiple edges between the same pair of vertices, those edges may carry different weights.
For example, two transportation services may both connect \(A\) and \(B\) but have different costs or travel times.
The graph type and the meaning of each edge must therefore be specified clearly.
Changing Weights without Changing Structure
A graph may keep the same vertices and edges while its weights change.
For example, a road network may have the same roads tomorrow, but travel times may differ because of traffic.
Thus, graph structure and edge data are related but distinct layers of the model.
Comparing Two Paths
Suppose two paths connect \(A\) to \(D\).
Path \(P_1\) has edge weights
\[ 4,\qquad7, \]so
\[ w(P_1)=11. \]Path \(P_2\) has edge weights
\[ 3,\qquad2,\qquad4, \]so
\[ w(P_2)=9. \]If the weights are additive costs, \(P_2\) has the lower total cost.
Local Weight versus Total Route Weight
Choosing the smallest available edge at each step does not automatically produce the smallest total route weight.
A locally inexpensive edge may lead into a region where later edges are very expensive.
This distinction motivates systematic shortest-path algorithms.
Example: A Local Choice Can Mislead
From \(A\), suppose one edge to \(B\) has weight \(1\), while an edge to \(C\) has weight \(4\).
If the remaining edge from \(B\) to the destination has weight \(20\), then the route through \(B\) costs
\[ 1+20=21. \]If the remaining edge from \(C\) costs \(3\), then the route through \(C\) costs
\[ 4+3=7. \]The smallest first edge did not produce the smallest total.
Common Error: Ignoring Units
A weight of \(10\) has no operational meaning without knowing what it measures.
Do not compare
\[ 10\text{ minutes} \]directly with
\[ 8\text{ dollars} \]as if the two values were the same kind of quantity.
Common Error: Treating Weight as Edge Count
An edge labeled \(5\) is still one edge.
Its weight is \(5\); its contribution to the number of edges is \(1\).
Therefore, edge weights do not directly change vertex degree.
Common Error: Assuming Every Weight Is a Cost
A large edge weight might be undesirable if it measures travel time, but desirable if it measures capacity.
Interpret the meaning of the weight before deciding whether larger or smaller is preferable.
Common Error: Adding Incompatible Quantities
A route cannot meaningfully combine a distance weight and a monetary-cost weight by simple addition unless the model deliberately converts them into a common scale.
Edge weights in one optimization calculation should normally represent compatible quantities.
Common Error: Confusing Zero Weight with No Edge
If zero is allowed as a legitimate edge weight, then an entry of \(0\) in a matrix cannot simultaneously be assumed to mean “no connection.”
The representation must use a separate convention for absent edges.
Common Error: Assuming Reverse Weights Match
In an undirected graph, the same edge has the same weight in either reading direction.
In a directed graph, however,
\[ w(u,v) \]and
\[ w(v,u) \]may be different because they belong to different directed edges.
A Reliable Procedure for Reading a Weighted Graph
- Identify the vertices and edges.
- Determine whether the graph is directed or undirected.
- Identify what each weight represents.
- Record the units of the weights when appropriate.
- Determine whether larger or smaller values are preferable.
- Determine how weights combine along a route.
- Distinguish path length from total path weight.
- Check how missing edges and zero weights are represented.
Example: Full Weighted-Graph Workflow
Suppose a transportation graph has
\[ V=\{A,B,C,D\} \]and weighted edges
\[ w(A,B)=6,\qquad w(A,C)=3,\qquad w(B,D)=4,\qquad w(C,D)=5. \]Assume the weights are travel times in minutes.
The route
\[ A\to B\to D \]has total weight
\[ 6+4=10. \]The route
\[ A\to C\to D \]has total weight
\[ 3+5=8. \]Therefore, among these two routes, \(A\to C\to D\) has the smaller modeled travel time.
Practice 1: Interpret a Weight
An edge between two cities has weight \(35\), and the model states that weights measure miles.
What does the number \(35\) mean?
Practice 2: Path Weight
A path contains edges with weights
\[ 4,\qquad6,\qquad3. \]Find the total path weight using additive weights.
Practice 3: Path Length versus Weight
A path uses four edges with weights
\[ 2,\qquad5,\qquad1,\qquad7. \]Find its path length and its total path weight.
Practice 4: Compare Two Routes
Route \(P_1\) has edge weights \(8\) and \(6\).
Route \(P_2\) has edge weights \(4\), \(3\), and \(5\).
Which route has the smaller total weight?
Practice 5: Directed Weights
A directed graph contains
\[ w(A,B)=5 \]and
\[ w(B,A)=9. \]Are these values contradictory?
Practice 6: Weighted Adjacency List
Let the undirected weighted edges be
\[ w(A,B)=2,\qquad w(A,C)=6,\qquad w(B,C)=4. \]Write the weighted adjacency list for \(A\).
Practice 7: Weighted Matrix
Using vertex order \(A,B,C\) and \(0\) for no edge, write the weighted adjacency matrix for
\[ w(A,B)=3,\qquad w(B,C)=7, \]where the graph is undirected.
Practice 8: Zero-Weight Edge
If a graph permits legitimate edges of weight \(0\), why can \(0\) be a poor choice for representing a missing edge in its matrix?
Practice 9: Choose the Better Weight
Two network links have capacities \(40\) and \(65\) units per second.
If greater capacity is preferred, which edge has the more favorable weight?
Practice 10: Identify the Error
A student sees one edge labeled \(12\) and says, “That contributes twelve edges to the degree of each endpoint.”
Explain the error.
Practice Answers
Practice 1
The edge represents a connection whose modeled distance is
\[ \boxed{35\text{ miles}}. \]Practice 2
Add the edge weights:
\[ \boxed{4+6+3=13}. \]Practice 3
The path uses four edges, so its length is
\[ \boxed{4}. \]Its total weight is
\[ 2+5+1+7=15, \]so
\[ \boxed{w(P)=15}. \]Practice 4
For \(P_1\),
\[ 8+6=14. \]For \(P_2\),
\[ 4+3+5=12. \]Therefore,
\[ \boxed{P_2\text{ has the smaller total weight}}. \]Practice 5
No. In a directed graph, \(A\to B\) and \(B\to A\) are different directed edges, so they may carry different weights.
\[ \boxed{w(A,B)\ne w(B,A)\text{ is allowed}}. \]Practice 6
Vertex \(A\) is adjacent to \(B\) with weight \(2\) and to \(C\) with weight \(6\):
\[ \boxed{A:\ (B,2),(C,6)}. \]Practice 7
Using vertex order \(A,B,C\),
\[ \boxed{ W= \begin{pmatrix} 0&3&0\\ 3&0&7\\ 0&7&0 \end{pmatrix} }. \]Practice 8
If \(0\) can be a real edge weight, then a matrix entry of \(0\) would be ambiguous: it could mean either a zero-weight edge or no edge at all.
A different symbol or convention should be used for missing edges.
Practice 9
Since greater capacity is preferred,
\[ \boxed{65\text{ units per second}} \]is the more favorable weight.
Practice 10
The label \(12\) is the numerical weight of one edge. It does not mean that twelve separate edges exist.
That edge contributes
\[ \boxed{1} \]to the degree of each endpoint in an ordinary undirected graph.
What to Remember
- A weighted graph attaches numerical values to edges.
- A weight function can be written \(w:E\to\mathbb{R}\).
- Weights may represent distance, cost, time, capacity, strength, or other quantities.
- The meaning and units of a weight must be stated by the model.
- For additive quantities, path weight is the sum of the edge weights used.
- Path length and path weight are different concepts.
- In directed graphs, opposite edges may have different weights.
- Zero-weight edges require care when matrices use \(0\) for missing connections.
- Not every type of weight should be combined by simple addition.
Where We Go Next
Weighted graphs enrich edges with numerical information, but we still need precise language for moving through a graph.
The next lesson, Paths, Walks, Trails, Circuits, and Connectivity, develops the structures used to describe movement through networks and determine whether vertices can reach one another.