Data Structures
Weighted Graph Representation
Difficulty: Intermediate
Highways have lengths in kilometers, flights have ticket prices in dollars, and network links have latencies in milliseconds. Treating any of those graphs as unweighted throws away the only information that matters for the question you...
Weighted Graph Representation
Highways have lengths in kilometers, flights have ticket prices in dollars, and network links have latencies in milliseconds. Treating any of those graphs as unweighted throws away the only information that matters for the question you actually care about (the shortest, cheapest, or fastest route), which is exactly the gap a Weighted Graph representation closes by attaching a number to every edge.
This lesson covers three representations: a weighted adjacency list backed by arrays of {node, weight} pairs, a weighted adjacency matrix where matrix[u][v] is the edge cost (and infinity for non-edges), and a weighted edge list that stores (u, v, weight) triples. You will analyze the space and time trade-offs, see why Dijkstra wants the adjacency list, why Floyd-Warshall wants the matrix, and why Kruskal wants the edge list, and you will represent both directed and undirected weighted graphs correctly in each format.
In Graphs: Representation Basics, you stored connectivity (whether an edge exists) using the same three shapes; the weighted version simply replaces a boolean or membership check with a numeric value. Hash Map (Dictionary) Basics is what makes the adjacency list work: a vertex maps to its neighbor-and-weight list in expected O(1), the same way the unweighted version did.
With weights in the picture, the algorithms track unlocks shortest-path and minimum-spanning-tree algorithms that read the weight on every edge during their core inner loop.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Explain what a weighted edge is and how weights model real-world costs such as distance, time, or capacity.
Build a weighted adjacency list using arrays of {node, weight} objects in JavaScript and Python.
Build a weighted adjacency matrix and explain its advantages for dense graphs and O(1) edge-weight queries.
Construct a weighted edge list and describe when it is preferred (e.g., Kruskal's MST).
Represent both directed and undirected weighted graphs in all three formats.
Compare the three weighted representations in terms of space, edge lookup, neighbor iteration, and algorithm suitability.
Why This Matters
01
Nearly every real-world graph problem involves weights -- road distances between cities, flight costs between airports, latency between servers, or bandwidth on network links. The unweighted representations from the basics lesson are not enough once edges carry a cost.
02
Choosing the right weighted representation directly determines the efficiency of algorithms you run on top of it: Dijkstra needs fast neighbor-with-weight iteration (adjacency list), Floyd-Warshall needs O(1) edge lookups (adjacency matrix), and Kruskal needs edges sorted by weight (edge list).
03
Interview problems involving shortest paths, minimum spanning trees, and network flow all begin with constructing a weighted graph. Understanding representation trade-offs is a prerequisite for every intermediate and advanced graph algorithm.
Key Terms
8 terms you'll encounter in this lesson
Weighted Edge
An edge that carries a numeric value (weight) representing a cost, distance, time, or capacity. In an unweighted graph every edge implicitly has weight 1.
Weighted Adjacency List
A graph representation where each vertex stores a list of (neighbor, weight) pairs. Uses O(V + E) space and supports efficient neighbor iteration with weights.
Weighted Adjacency Matrix
A V x V matrix where entry [i][j] stores the weight of the edge from vertex i to vertex j, or Infinity (or a sentinel like -1) if no edge exists. Uses O(V^2) space.
Weighted Edge List
A flat list of (source, destination, weight) triples. Compact for sparse graphs and ideal for algorithms that process edges globally (e.g., sorting edges by weight in Kruskal's MST).
Negative Weight
An edge with a weight less than zero. Negative weights arise in finance (arbitrage) and certain optimization problems. Dijkstra cannot handle them; Bellman-Ford can.
Shortest Path
The path between two vertices whose total edge weight is minimized. Dijkstra finds shortest paths from a single source in non-negative-weight graphs; Bellman-Ford handles negative weights.
Minimum Spanning Tree (MST)
A subset of edges that connects all vertices with the minimum total weight and no cycles. Kruskal's and Prim's algorithms find the MST of an undirected weighted graph.
Sentinel Value
A special marker (like Infinity, -1, or null) used in adjacency matrices to indicate 'no edge exists' between two vertices, as opposed to a weight of 0.
Heads Up
Common misconceptions to watch out for
"Zero weight means no edge"
A weight of 0 is a valid edge cost (e.g., free transfer between subway lines). Use Infinity or null as the sentinel for 'no edge' in an adjacency matrix -- never 0.
"Weighted graphs are always directed"
Weighted graphs can be directed or undirected. An undirected weighted edge between A and B means the cost is the same in both directions. In an adjacency list you add the weight to both A's and B's neighbor lists; in a matrix you set both [A][B] and [B][A].
"You can always use Dijkstra on any weighted graph"
Dijkstra requires non-negative edge weights. If any edge has a negative weight, Dijkstra can produce incorrect shortest paths. Use Bellman-Ford for graphs with negative weights.
"Adjacency matrix wastes space even for weighted graphs"
For dense weighted graphs (where most vertex pairs are connected) the matrix is space-competitive with lists and gives O(1) edge-weight lookup. The 'waste' only applies to sparse graphs.