15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
A weighted graph gives every edge a number, called its weight. You write A-B:4 for an undirected edge between A and B with weight 4. The total weight of a path is the sum of its edge weights, and a path with fewer edges can cost more than a longer one.
| Edge notation | A-B:4 means an edge between A and B with weight 4 |
|---|---|
| List entry | (neighbor, weight) pair, kept together |
| Path cost | Sum of the weights on its consecutive edges |
| Build time and space | O(V + E) |
| Cost of a k-edge path | O(k), given constant-time weight lookup |
| Matrix note | Use a no-edge marker distinct from every weight, since 0 can be a real weight |
You should already be able to name vertices and edges, build adjacency lists and matrices, and recognize that BFS and DFS visit graph structure.
Here, each edge also carries a number.
A weighted edge has:
A and B4Write A-B:4 to mean that the undirected edge between A and B has weight 4.
The weight is an attribute of the edge. It is a property of neither vertex.
A path is a sequence of vertices connected by edges. Its total weight is the sum of the weights on its consecutive edges.
For example, if a path uses edges with weights 1, 1, and 2, its total weight is:
The same path has three edges.
BFS layers measure the number of edges from a start vertex. They do not generally measure the smallest total weight when edges can have different weights.
Use this undirected weighted graph throughout the lesson:
1A-B:4, A-C:1, C-B:1, B-D:2, C-D:5Read each edge carefully:
| Edge | Weight |
|---|---|
| A-B | 4 |
| A-C | 1 |
| C-B | 1 |
| B-D | 2 |
| C-D | 5 |
Because the graph is undirected, A-B:4 means:
A, you can reach B with weight 4B, you can reach A with weight 4A weighted adjacency-list entry must keep the neighbor and weight together.
1A: [(B,4), (C,1)]
2B: [(A,4), (C,1), (D,2)]
3C: [(A,1), (B,1), (D,5)]
4D: [(B,2), (C,5)]The pair (B,4) means “neighbor B through an edge of weight 4.”
First build the adjacency list. Then compare three paths from A to D.
From A to D: A-B-D has 2 edges, weight 4 + 2 = 6; A-C-B-D has 3 edges, weight 1 + 1 + 2 = 4; A-C-D has 2 edges, weight 1 + 5 = 6. Fewest edges is not lowest weight.
1A-B has weight 4
2A-C has weight 1
3C-B has weight 1
4B-D has weight 2
5C-D has weight 5At this point, there are no adjacency-list entries yet.
Start with one empty bucket per vertex:
1A: []
2B: []
3C: []
4D: []Process A-B:4.
Because the edge is undirected, add two entries:
1A: [(B,4)]
2B: [(A,4)]
3C: []
4D: []Process A-C:1.
1A: [(B,4), (C,1)]
2B: [(A,4)]
3C: [(A,1)]
4D: []Process C-B:1.
1A: [(B,4), (C,1)]
2B: [(A,4), (C,1)]
3C: [(A,1), (B,1)]
4D: []Process B-D:2.
1A: [(B,4), (C,1)]
2B: [(A,4), (C,1), (D,2)]
3C: [(A,1), (B,1)]
4D: [(B,2)]Process C-D:5.
1A: [(B,4), (C,1)]
2B: [(A,4), (C,1), (D,2)]
3C: [(A,1), (B,1), (D,5)]
4D: [(B,2), (C,5)]Every neighbor remains paired with the weight of the edge that reaches it.
The path is:
1A → B → DIts edges are:
1A-B with weight 4
2B-D with weight 2Add each path-edge weight once:
1total = 4 + 2 = 6This path uses 2 edges and has total weight 6.
The path is:
1A → C → B → DIts edges are:
1A-C with weight 1
2C-B with weight 1
3B-D with weight 2Add them:
1total = 1 + 1 + 2 = 4This path uses 3 edges and has total weight 4.
The path is:
1A → C → DIts edges are:
1A-C with weight 1
2C-D with weight 5Add them:
1total = 1 + 5 = 6This path uses 2 edges and has total weight 6.
| Path | Edge count | Total weight |
|---|---|---|
| A-B-D | 2 | 6 |
| A-C-B-D | 3 | 4 |
| A-C-D | 2 | 6 |
A-B-D has fewer edges than A-C-B-D.
A-C-B-D has the lower total weight.
Ordinary BFS distance does not answer general weighted path-cost questions. BFS sees A-B-D at distance 2 edges. BFS does not add 4 + 2 and compare that sum against 1 + 1 + 2.
While building an undirected weighted adjacency list, each input edge u-v with weight w must be readable in both directions:
1from u: (v,w)
2from v: (u,w)For the example, C-D:5 appears as:
1C: ..., (D,5)
2D: ..., (C,5)While evaluating a displayed path, the running total must equal the sum of exactly the weights on the path edges already processed.
For path A-C-B-D, the running states are:
| Processed path portion | Weights added | Running total |
|---|---|---|
| A | none | 0 |
| A-C | 1 | 1 |
| A-C-B | 1, 1 | 2 |
| A-C-B-D | 1, 1, 2 | 4 |
The invariant is:
The weight of a displayed path is the sum of exactly the weights on its consecutive path edges. In an undirected weighted representation, edge
u-vwith weightwis readable as both(v,w)fromuand(u,w)fromv.
Before adding a weight, confirm that the consecutive pair is an edge. Otherwise, the sequence has no valid path total.
The algorithm needs two operations.
For every vertex, create an empty list.
For every undirected weighted edge (u, v, w):
(v, w) to u’s list(u, w) to v’s listDo not store just v in u’s list. The weight belongs with that particular connection.
Given a path such as:
1[A, C, B, D]start with:
1total = 0Then inspect each consecutive pair:
1(A, C)
2(C, B)
3(B, D)For each pair:
totalA one-vertex path such as [A] contains no edges, so its total is 0.
A weighted adjacency matrix stores a weight in cell [u][v].
For example:
1matrix[A][C] = 1
2matrix[C][A] = 1A missing edge needs a value distinct from every allowed edge weight.
If zero-weight edges are allowed, 0 cannot also mean “no edge.” Use a separate no-edge marker, such as no entry or infinity.
If both A-B:2 and A-B:5 exist, a list can store both:
1A: [(B,2), (B,5)]
2B: [(A,2), (A,5)]A path written only as [A, B] does not identify which parallel edge it uses. The representation and path format must state a policy. For example, a path can identify a specific edge entry, or the input can prohibit parallel edges.
The first procedure builds the weighted adjacency list.
1procedure buildUndirectedWeightedAdjacencyList(vertices, edges) -> adjacency
2 input:
3 vertices: collection of vertex labels
4 edges: collection of triples (u, v, weight)
5 returns:
6 adjacency: mapping from each vertex to a list of (neighbor, weight) pairs
7 mutation:
8 creates and returns a new mapping; does not mutate vertices or edges
9 boundary:
10 an isolated vertex receives an empty list
11
12 1. adjacency <- empty mapping
13
14 2. for each vertex in vertices
15 3. adjacency[vertex] <- empty list
16
17 4. for each (u, v, weight) in edges
18 5. append (v, weight) to adjacency[u]
19 6. append (u, weight) to adjacency[v]
20
21 7. return adjacencyThe next helper finds the weight for one directed adjacency-list lookup.
1function edgeWeight(adjacency, fromVertex, toVertex) -> weight or MISSING
2 input:
3 adjacency: weighted adjacency list
4 fromVertex, toVertex: endpoints to check
5 returns:
6 the weight stored with toVertex in fromVertex's list,
7 or MISSING when no such adjacency entry exists
8 mutation:
9 does not mutate adjacency
10 contract:
11 for a graph with parallel edges, the caller must identify which edge
12 is intended, or the graph input must prohibit parallel edges
13
14 1. for each (neighbor, weight) in adjacency[fromVertex]
15 2. if neighbor = toVertex
16 3. return weight
17
18 4. return MISSINGFinally, compute the total cost of a supplied path.
1function weightedPathCost(adjacency, path) -> total or INVALID_PATH
2 input:
3 adjacency: weighted adjacency list
4 path: ordered sequence of vertices
5 returns:
6 sum of the edge weights for a valid path;
7 INVALID_PATH if any consecutive pair has no edge
8 mutation:
9 does not mutate adjacency or path
10 boundaries:
11 an empty path returns 0
12 a one-vertex path returns 0
13 zero is accepted as a valid edge weight
14
15 1. total <- 0
16
17 2. for i <- 0 to length(path) - 2
18 3. fromVertex <- path[i]
19 4. toVertex <- path[i + 1]
20 5. weight <- edgeWeight(adjacency, fromVertex, toVertex)
21
22 6. if weight = MISSING
23 7. return INVALID_PATH
24
25 8. total <- total + weight
26
27 9. return totalUse the original weighted adjacency list:
1A: [(B,4), (C,1)]
2B: [(A,4), (C,1), (D,2)]
3C: [(A,1), (B,1), (D,5)]
4D: [(B,2), (C,5)]Evaluate:
1path = [A, C, B, D]The path has three edges, so line 2 runs with i = 0, i = 1, and i = 2.
| Pseudocode line | State |
|---|---|
| 1 | total = 0 |
| 2 | Start loop with i = 0. |
| 3 | fromVertex = path[0] = A |
| 4 | toVertex = path[1] = C |
| 5 | Call edgeWeight(adjacency, A, C). Scan A’s entries: (B,4) does not match C; (C,1) matches. Return 1. |
| 6 | weight is not MISSING. |
| 8 | total = 0 + 1 = 1 |
| 2 | Continue with i = 1. |
| 3 | fromVertex = path[1] = C |
| 4 | toVertex = path[2] = B |
| 5 | Call edgeWeight(adjacency, C, B). Scan C’s entries: (A,1) does not match B; (B,1) matches. Return 1. |
| 6 | weight is not MISSING. |
| 8 | total = 1 + 1 = 2 |
| 2 | Continue with i = 2. |
| 3 | fromVertex = path[2] = B |
| 4 | toVertex = path[3] = D |
| 5 | Call edgeWeight(adjacency, B, D). Scan B’s entries: (A,4) does not match D; (C,1) does not match D; (D,2) matches. Return 2. |
| 6 | weight is not MISSING. |
| 8 | total = 2 + 2 = 4 |
| 2 | The next value would be i = 3, but length(path) - 2 = 2. Stop the loop. |
| 9 | Return 4. |
The result is:
1weightedPathCost(adjacency, [A, C, B, D]) = 4Now consider the boundary case:
1path = [A]Line 1 sets total to 0.
At line 2, the loop has no consecutive pair to process. Line 9 returns:
10Before processing any edges, every vertex has an empty bucket. No processed edge is missing because no edge has been processed.
When the algorithm processes an undirected edge (u, v, w), it adds:
1(v, w) to adjacency[u]
2(u, w) to adjacency[v]The processed edge is readable from either endpoint, and both entries carry the same weight w.
After all edges are processed, every input edge has exactly the required directional entries. Therefore, the returned adjacency list represents every undirected weighted edge with its weight attached to its neighbor relationship.
Before the loop starts, no path edge has been processed and total = 0. This equals the sum of zero weights, so the invariant holds.
Suppose the invariant holds before one loop iteration: total equals the sum of all earlier consecutive path edges.
The iteration examines exactly one new consecutive pair:
1(path[i], path[i + 1])If no such edge exists, the sequence is not a valid path. Returning INVALID_PATH is correct.
If the edge exists, the algorithm retrieves its weight and adds it once to total. Now total equals the sum of all previously processed edges plus the new path edge. The invariant is preserved.
The loop stops after every consecutive pair has been checked. At that point, every path edge has been added exactly once. Therefore, the returned total is the total weight of the supplied valid path.
First, the algorithm creates one empty list for each of the V vertices.
1V bucket initializationsThen it processes each of the E undirected edges once. Each edge causes two constant-size tuple insertions.
12E neighbor-weight insertionsSo the building work is:
The resulting list stores one bucket per vertex and two entries per undirected edge:
The returned representation uses that storage.
Suppose the path has k edges.
The loop processes exactly k consecutive pairs.
If every path edge already supplies its weight, or a constant-time edge lookup is available, each iteration does constant work:
The procedure uses a few variables:
1total, i, fromVertex, toVertex, weightSo its auxiliary space is:
The edgeWeight helper shown in the pseudocode scans a vertex’s adjacency list. With that helper, a lookup can take as many steps as the degree of fromVertex. The O(k) path-cost bound applies when each supplied path edge provides its weight or the representation provides constant-time lookup.
A basic BFS or DFS over a weighted adjacency list still examines each stored neighbor-weight entry once. It performs:
1V vertex-level work
2plus
3stored adjacency-entry workFor an undirected graph, that is proportional to V + E:
Traversal order does not by itself compare sums of edge weights. In the example, BFS can prefer the two-edge route A-B-D over the three-edge route A-C-B-D, even though their total weights are 6 and 4.
Incorrect assumption
1A: [B, C]Small exposing input
1A-B:4, A-C:1Wrong state or result
The representation says that B and C are neighbors of A, but it cannot tell whether A-B costs 4 or 1. A path-cost procedure has no weight to add.
Correction
Store neighbor-weight pairs:
1A: [(B,4), (C,1)]Incorrect matrix rule
1matrix[u][v] = 0 means no edgeSmall exposing input
1A-B:0Wrong state or result
1matrix[A][B] = 0The matrix cannot distinguish “there is an A-B edge costing zero” from “there is no A-B edge.” It may incorrectly report that the edge is missing.
Correction
Use a missing-edge sentinel distinct from valid weights:
1matrix[A][B] = 0 // real zero-weight edge
2matrix[A][C] = infinity // no edgeA no-entry representation can also distinguish these cases.
Incorrect assumption
1A path with fewer edges is automatically cheaper.Small exposing input
1A-B:4, A-C:1, C-B:1, B-D:2Wrong result
1A-B-D has 2 edges and total weight 6
2A-C-B-D has 3 edges and total weight 4Choosing A-B-D because it uses two edges gives the wrong lower-cost choice.
Correction
When weights matter, add the edge weights:
1A-B-D: 4 + 2 = 6
2A-C-B-D: 1 + 1 + 2 = 4Incorrect operation
1total <- total + fromVertex + toVertexSmall exposing input
1path A-C-B-D with edge weights 1, 1, 2Wrong result
Vertex labels are not the path cost. The operation produces a nonnumeric or unrelated value.
Correction
Look up and add only the weights on consecutive path edges:
11 + 1 + 2 = 4Incorrect operation
1total <- total + assumedWeight(C, B)without first confirming that C-B exists.
Small exposing input
1Edges: A-C:1
2Path: A-C-BWrong state or result
A-C exists, but C-B does not. Returning a numeric total would treat a nonexistent edge as part of a path.
Correction
For every consecutive pair, perform the edge lookup first. If it returns MISSING, return INVALID_PATH.
Incorrect construction
Create buckets only for vertices that appear in an edge.
Small exposing input
1Vertices: A, B, E
2Edges: A-B:4Wrong state or result
Vertex E disappears from the representation.
Correction
Initialize a bucket for every supplied vertex:
1E: []E has no path to another vertex through this graph.
Implement:
1weightedPathCost(weightedAdjacencyList, path)Contract to test:
path is an edge.0.0 to the total.There is no mapped executable problem for this lesson.
Sources used for representation and traversal context:
1def build(vertices, edges):
2 adj = {v: [] for v in vertices} # isolated vertices keep an empty list
3 for u, v, w in edges:
4 adj[u].append((v, w)) # keep the weight with the neighbor
5 adj[v].append((u, w))
6 return adj
7
8def edge_weight(adj, a, b):
9 for neighbor, weight in adj[a]:
10 if neighbor == b:
11 return weight
12 return None # missing edge, not weight 0
13
14def path_cost(adj, path):
15 total = 0
16 for i in range(len(path) - 1):
17 weight = edge_weight(adj, path[i], path[i + 1])
18 if weight is None:
19 return None # invalid path
20 total += weight
21 return total
22
23edges = [("A", "B", 4), ("A", "C", 1), ("C", "B", 1), ("B", "D", 2), ("C", "D", 5)]
24adj = build(["A", "B", "C", "D"], edges)
25for v, entries in adj.items():
26 print(f"{v}:", " ".join(f"({n},{w})" for n, w in entries))
27for path in (["A", "B", "D"], ["A", "C", "B", "D"], ["A", "C", "D"], ["A", "D"]):
28 cost = path_cost(adj, path)
29 print("-".join(path) + ":", "invalid" if cost is None else cost)1import java.util.*;
2
3public class Main {
4 static class Edge {
5 final String to;
6 final int weight;
7
8 Edge(String to, int weight) {
9 this.to = to;
10 this.weight = weight;
11 }
12 }
13
14 static Map<String, List<Edge>> build(String[] vertices, Object[][] edges) {
15 Map<String, List<Edge>> adj = new LinkedHashMap<>();
16 for (String v : vertices) adj.put(v, new ArrayList<>()); // isolated vertices keep a list
17 for (Object[] e : edges) {
18 String u = (String) e[0], v = (String) e[1];
19 int w = (Integer) e[2];
20 adj.get(u).add(new Edge(v, w)); // keep the weight with the neighbor
21 adj.get(v).add(new Edge(u, w));
22 }
23 return adj;
24 }
25
26 static Integer edgeWeight(Map<String, List<Edge>> adj, String a, String b) {
27 for (Edge e : adj.get(a)) {
28 if (e.to.equals(b)) return e.weight;
29 }
30 return null; // missing edge, not weight 0
31 }
32
33 static Integer pathCost(Map<String, List<Edge>> adj, String[] path) {
34 int total = 0;
35 for (int i = 0; i + 1 < path.length; i++) {
36 Integer weight = edgeWeight(adj, path[i], path[i + 1]);
37 if (weight == null) return null; // invalid path
38 total += weight;
39 }
40 return total;
41 }
42
43 public static void main(String[] args) {
44 Object[][] edges = {{"A", "B", 4}, {"A", "C", 1}, {"C", "B", 1}, {"B", "D", 2}, {"C", "D", 5}};
45 Map<String, List<Edge>> adj = build(new String[]{"A", "B", "C", "D"}, edges);
46 for (Map.Entry<String, List<Edge>> entry : adj.entrySet()) {
47 StringBuilder sb = new StringBuilder();
48 for (Edge e : entry.getValue()) sb.append(" (").append(e.to).append(",").append(e.weight).append(")");
49 System.out.println(entry.getKey() + ":" + sb);
50 }
51 String[][] paths = {{"A", "B", "D"}, {"A", "C", "B", "D"}, {"A", "C", "D"}, {"A", "D"}};
52 for (String[] path : paths) {
53 Integer cost = pathCost(adj, path);
54 System.out.println(String.join("-", path) + ": " + (cost == null ? "invalid" : cost));
55 }
56 }
57}1#include <iostream>
2#include <map>
3#include <optional>
4#include <string>
5#include <tuple>
6#include <utility>
7#include <vector>
8using namespace std;
9
10using Adj = map<string, vector<pair<string, int>>>;
11
12Adj build(const vector<string>& vertices, const vector<tuple<string, string, int>>& edges) {
13 Adj adj;
14 for (const string& v : vertices) adj[v]; // isolated vertices keep a list
15 for (const auto& e : edges) {
16 adj[get<0>(e)].push_back({get<1>(e), get<2>(e)}); // keep the weight with the neighbor
17 adj[get<1>(e)].push_back({get<0>(e), get<2>(e)});
18 }
19 return adj;
20}
21
22optional<int> edgeWeight(const Adj& adj, const string& a, const string& b) {
23 for (const auto& entry : adj.at(a)) {
24 if (entry.first == b) return entry.second;
25 }
26 return nullopt; // missing edge, not weight 0
27}
28
29optional<int> pathCost(const Adj& adj, const vector<string>& path) {
30 int total = 0;
31 for (size_t i = 0; i + 1 < path.size(); i++) {
32 auto weight = edgeWeight(adj, path[i], path[i + 1]);
33 if (!weight) return nullopt; // invalid path
34 total += *weight;
35 }
36 return total;
37}
38
39int main() {
40 vector<tuple<string, string, int>> edges = {
41 {"A", "B", 4}, {"A", "C", 1}, {"C", "B", 1}, {"B", "D", 2}, {"C", "D", 5}};
42 Adj adj = build({"A", "B", "C", "D"}, edges);
43 for (const auto& kv : adj) {
44 cout << kv.first << ":";
45 for (const auto& e : kv.second) cout << " (" << e.first << "," << e.second << ")";
46 cout << "\n";
47 }
48 vector<vector<string>> paths = {{"A", "B", "D"}, {"A", "C", "B", "D"}, {"A", "C", "D"}, {"A", "D"}};
49 for (const auto& path : paths) {
50 for (size_t i = 0; i < path.size(); i++) cout << (i ? "-" : "") << path[i];
51 auto cost = pathCost(adj, path);
52 cout << ": ";
53 if (cost) cout << *cost; else cout << "invalid";
54 cout << "\n";
55 }
56}1function build(vertices, edges) {
2 const adj = new Map(vertices.map((v) => [v, []])); // isolated vertices keep a list
3 for (const [u, v, w] of edges) {
4 adj.get(u).push([v, w]); // keep the weight with the neighbor
5 adj.get(v).push([u, w]);
6 }
7 return adj;
8}
9
10function edgeWeight(adj, a, b) {
11 for (const [neighbor, weight] of adj.get(a)) {
12 if (neighbor === b) return weight;
13 }
14 return null; // missing edge, not weight 0
15}
16
17function pathCost(adj, path) {
18 let total = 0;
19 for (let i = 0; i + 1 < path.length; i++) {
20 const weight = edgeWeight(adj, path[i], path[i + 1]);
21 if (weight === null) return null; // invalid path
22 total += weight;
23 }
24 return total;
25}
26
27const edges = [['A', 'B', 4], ['A', 'C', 1], ['C', 'B', 1], ['B', 'D', 2], ['C', 'D', 5]];
28const adj = build(['A', 'B', 'C', 'D'], edges);
29for (const [v, entries] of adj) {
30 console.log(`${v}: ${entries.map(([n, w]) => `(${n},${w})`).join(' ')}`);
31}
32for (const path of [['A', 'B', 'D'], ['A', 'C', 'B', 'D'], ['A', 'C', 'D'], ['A', 'D']]) {
33 const cost = pathCost(adj, path);
34 console.log(`${path.join('-')}: ${cost === null ? 'invalid' : cost}`);
35}In an unweighted graph an edge only says two vertices are connected, so distance counts edges. In a weighted graph each edge carries a number, and a path costs the sum of those numbers.
It is built for weighted graphs with nonnegative weights. On an unweighted graph, BFS already gives the fewest edges. BFS cannot compare 4 + 2 against 1 + 1 + 2, which is why weighted shortest paths need another algorithm.
Yes. Weight is a property of an edge, so a graph with no self-loops and no parallel edges can still be weighted. Parallel edges A-B:2 and A-B:5 make the path [A, B] ambiguous, so some inputs prohibit them.
Weight is a number on an edge. Direction is which way you may travel it. They are independent, so a graph can be weighted, directed, both or neither. The edges in this lesson are undirected and weighted.
No. In the example, A-B-D uses 2 edges and costs 4 + 2 = 6. A-C-B-D uses 3 edges and costs 1 + 1 + 2 = 4.