Weighted Graph from Scratch (2026)
A weighted graph assigns a numerical weight to each edge, representing cost, distance, capacity, or any metric associated with the connection. Weighted graphs are essential for modeling real-world networks like roads with distances, computer networks with latency, social networks with relationship strength, and supply chains with costs.
In this tutorial, we will explore how to represent weighted graphs using adjacency lists and matrices, implement operations like adding and removing edges, and demonstrate how weighted graphs enable algorithms like Dijkstra's shortest path and Minimum Spanning Tree.
Adjacency List Representation
An adjacency list stores for each vertex a list of its neighbors along with the edge weights. This representation is memory-efficient for sparse graphs, using O(V + E) space. Each vertex maps to a list of (neighbor, weight) pairs. Adding edges is O(1), checking for an edge is O(degree), and iterating all edges is O(V + E).
This is the most common representation for weighted graphs in practice. It handles directed and undirected graphs naturally.
#include
#include
#include
using namespace std;
struct Edge { int to; int weight; };
class WeightedGraph {
int V;
vector> adj;
public:
WeightedGraph(int v) : V(v), adj(v) {}
void addEdge(int u, int v, int w) {
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
void display() {
for (int i = 0; i < V; i++) {
cout << i << " -> ";
for (auto& e : adj[i])
cout << "(" << e.to << "," << e.weight << ") ";
cout << endl;
}
}
};
Adjacency Matrix Representation
An adjacency matrix uses a 2D array where matrix[i][j] stores the weight of the edge from vertex i to vertex j. A special value (infinity) indicates no edge. This representation uses O(V^2) space regardless of the number of edges, making it suitable for dense graphs. Edge lookup is O(1), but iterating edges is always O(V^2).
Adjacency matrices are preferred when the graph is dense, when you need O(1) edge weight queries, or when using matrix-based algorithms like Floyd-Warshall.
import math
class WeightedGraphMatrix:
def __init__(self, vertices):
self.V = vertices
self.matrix = [[0 if i == j else math.inf
for j in range(vertices)]
for i in range(vertices)]
def add_edge(self, u, v, weight, directed=False):
self.matrix[u][v] = weight
if not directed:
self.matrix[v][u] = weight
def has_edge(self, u, v):
return self.matrix[u][v] != math.inf
def display(self):
for row in self.matrix:
print([w if w != math.inf else 'INF' for w in row])
graph = WeightedGraphMatrix(4)
graph.add_edge(0, 1, 5)
graph.add_edge(0, 2, 3)
graph.add_edge(1, 2, 1)
graph.add_edge(2, 3, 7)
graph.display()Dijkstra's Algorithm
Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights. It uses a priority queue to greedily select the vertex with the smallest tentative distance, then relaxes all its edges. The algorithm runs in O((V + E) log V) with a binary heap or O(V^2) with a simple array.
Dijkstra's does not work with negative edge weights. For graphs with negative weights, use Bellman-Ford. The algorithm maintains a distance array initialized to infinity except for the source (0).
import java.util.*;
class Dijkstra {
static int[] shortestPath(List> adj, int src) {
int V = adj.size();
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
PriorityQueue pq = new PriorityQueue<>((a,b) -> a[1]-b[1]);
pq.offer(new int[]{src, 0});
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int u = curr[0], d = curr[1];
if (d > dist[u]) continue;
for (int[] edge : adj.get(u)) {
int v = edge[0], w = edge[1];
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.offer(new int[]{v, dist[v]});
}
}
}
return dist;
}
} Weighted Graph Applications
Weighted graphs are used in GPS navigation (road distances), network routing (latency), airline scheduling (flight costs), social networks (relationship strength), and recommendation systems (similarity scores). Understanding weighted graph representations is crucial for implementing these algorithms efficiently.
Common algorithms on weighted graphs include Dijkstra's shortest path, Bellman-Ford for negative weights, Floyd-Warshall for all-pairs shortest paths, and Prim's/Kruskal's for minimum spanning trees.
import heapq
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
previous = {node: None for node in graph}
pq = [(0, start)]
while pq:
curr_dist, curr = heapq.heappop(pq)
if curr_dist > distances[curr]: continue
for nb, weight in graph[curr]:
dist = curr_dist + weight
if dist < distances[nb]:
distances[nb] = dist
previous[nb] = curr
heapq.heappush(pq, (dist, nb))
return distances, previous
def bellman_ford(vertices, edges, source):
dist = [float('inf')] * vertices
dist[source] = 0
for _ in range(vertices - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
for u, v, w in edges:
if dist[u] + w < dist[v]:
raise ValueError("Negative cycle detected")
return distFrequently Asked Questions
When to use adjacency list vs matrix?
Use adjacency list for sparse graphs (E << V^2) - it saves memory. Use adjacency matrix for dense graphs or when you need O(1) edge lookups. Matrix is also needed for Floyd-Warshall.
Does Dijkstra work with negative weights?
No. Dijkstra's greedy approach fails with negative weights because a path with more edges might have a smaller total weight. Use Bellman-Ford or SPFA for negative weights.
What is a weighted graph used for?
Modeling real-world networks with costs: GPS navigation (distances), network routing (latency), social networks (relationship strength), supply chains (transportation costs), and scheduling (time).
How to represent weighted edges?
In adjacency list, store (neighbor, weight) pairs. In adjacency matrix, store weight at matrix[i][j]. Use a special value (infinity or 0) to represent missing edges.
Originally published on Ayodhyyya. Last updated June 1, 2026.