Weighted Graph: Implementation and Applications

Key Insights

Weighted graphs model real-world problems where connections have costs, distances, or capacities—choosing the right representation (adjacency list vs. matrix) depends on graph density and your primary operations.
Dijkstra’s algorithm handles non-negative weights efficiently with O((V + E) log V) complexity, while Bellman-Ford sacrifices speed for the ability to detect negative cycles.
Minimum spanning trees solve network design problems optimally, and Kruskal’s algorithm with union-find provides an elegant O(E log E) solution that’s straightforward to implement.

Introduction to Weighted Graphs

A weighted graph assigns a numerical value to each edge, transforming simple connectivity into a rich model of real-world relationships. While an unweighted graph answers “can I get from A to B?”, a weighted graph answers “what’s the cost of getting from A to B?”

Consider road networks. Cities aren’t just connected—they’re connected by roads with specific distances. Network infrastructure has latency between nodes. Airlines price routes differently. Supply chains have shipping costs. All of these are weighted graph problems.

The weight can represent anything: distance, time, cost, capacity, probability, or bandwidth. This flexibility makes weighted graphs fundamental to optimization problems across domains.

Core Data Structures

Two primary representations dominate: adjacency matrices and adjacency lists. For weighted graphs, each has distinct trade-offs.

Adjacency Matrix: A 2D array where matrix[i][j] stores the weight between vertices i and j. Use a sentinel value (infinity or None) for non-edges.

Adjacency List: Each vertex maintains a list of (neighbor, weight) pairs. More memory-efficient for sparse graphs.

from typing import Dict, List, Tuple, Optional
import math

class WeightedGraphMatrix:
    """Adjacency matrix representation for weighted graphs."""
    
    def __init__(self, num_vertices: int):
        self.num_vertices = num_vertices
        # Initialize with infinity (no edge)
        self.matrix: List[List[float]] = [
            [math.inf] * num_vertices for _ in range(num_vertices)
        ]
        # Distance to self is 0
        for i in range(num_vertices):
            self.matrix[i][i] = 0
    
    def add_edge(self, u: int, v: int, weight: float, directed: bool = False) -> None:
        self.matrix[u][v] = weight
        if not directed:
            self.matrix[v][u] = weight
    
    def get_weight(self, u: int, v: int) -> float:
        return self.matrix[u][v]
    
    def has_edge(self, u: int, v: int) -> bool:
        return self.matrix[u][v] != math.inf and u != v


class WeightedGraphList:
    """Adjacency list representation for weighted graphs."""
    
    def __init__(self):
        self.adjacency: Dict[int, List[Tuple[int, float]]] = {}
    
    def add_vertex(self, v: int) -> None:
        if v not in self.adjacency:
            self.adjacency[v] = []
    
    def add_edge(self, u: int, v: int, weight: float, directed: bool = False) -> None:
        self.add_vertex(u)
        self.add_vertex(v)
        self.adjacency[u].append((v, weight))
        if not directed:
            self.adjacency[v].append((u, weight))
    
    def get_neighbors(self, v: int) -> List[Tuple[int, float]]:
        return self.adjacency.get(v, [])

When to use which:

Criteria	Adjacency Matrix	Adjacency List
Space	O(V²)	O(V + E)
Edge lookup	O(1)	O(degree)
All neighbors	O(V)	O(degree)
Best for	Dense graphs, frequent edge queries	Sparse graphs, traversals

Most real-world graphs are sparse. Social networks, road maps, and web graphs all have far fewer edges than V². Use adjacency lists as your default.

Building a Weighted Graph Class

Here’s a production-ready weighted graph implementation supporting both directed and undirected variants:

from typing import Dict, Set, List, Tuple, Optional, Iterator
from dataclasses import dataclass
import math

@dataclass
class Edge:
    destination: int
    weight: float

class WeightedGraph:
    """
    A flexible weighted graph supporting directed/undirected edges,
    vertex/edge removal, and common graph operations.
    """
    
    def __init__(self, directed: bool = False):
        self.directed = directed
        self._adjacency: Dict[int, Dict[int, float]] = {}
    
    @property
    def vertices(self) -> Set[int]:
        return set(self._adjacency.keys())
    
    @property
    def num_vertices(self) -> int:
        return len(self._adjacency)
    
    @property
    def num_edges(self) -> int:
        total = sum(len(neighbors) for neighbors in self._adjacency.values())
        return total if self.directed else total // 2
    
    def add_vertex(self, v: int) -> None:
        if v not in self._adjacency:
            self._adjacency[v] = {}
    
    def remove_vertex(self, v: int) -> None:
        if v not in self._adjacency:
            return
        # Remove all edges pointing to v
        for neighbors in self._adjacency.values():
            neighbors.pop(v, None)
        # Remove v and its outgoing edges
        del self._adjacency[v]
    
    def add_edge(self, u: int, v: int, weight: float) -> None:
        self.add_vertex(u)
        self.add_vertex(v)
        self._adjacency[u][v] = weight
        if not self.directed:
            self._adjacency[v][u] = weight
    
    def remove_edge(self, u: int, v: int) -> None:
        if u in self._adjacency:
            self._adjacency[u].pop(v, None)
        if not self.directed and v in self._adjacency:
            self._adjacency[v].pop(u, None)
    
    def get_weight(self, u: int, v: int) -> Optional[float]:
        if u in self._adjacency and v in self._adjacency[u]:
            return self._adjacency[u][v]
        return None
    
    def has_edge(self, u: int, v: int) -> bool:
        return u in self._adjacency and v in self._adjacency[u]
    
    def neighbors(self, v: int) -> Iterator[Tuple[int, float]]:
        if v in self._adjacency:
            for neighbor, weight in self._adjacency[v].items():
                yield neighbor, weight
    
    def edges(self) -> Iterator[Tuple[int, int, float]]:
        seen: Set[Tuple[int, int]] = set()
        for u, neighbors in self._adjacency.items():
            for v, weight in neighbors.items():
                edge = (min(u, v), max(u, v)) if not self.directed else (u, v)
                if edge not in seen:
                    seen.add(edge)
                    yield u, v, weight

This implementation uses a nested dictionary for O(1) edge lookups while maintaining efficient iteration. The Dict[int, float] inner structure prevents duplicate edges and makes weight updates trivial.

Shortest Path Algorithms

Finding the shortest path between vertices is the most common weighted graph operation. Two algorithms dominate: Dijkstra’s and Bellman-Ford.

Dijkstra’s Algorithm works when all edge weights are non-negative. It greedily selects the unvisited vertex with the smallest known distance, then relaxes all its edges. Using a priority queue yields O((V + E) log V) complexity.

import heapq
from typing import Dict, List, Tuple, Optional

def dijkstra(
    graph: WeightedGraph, 
    source: int
) -> Tuple[Dict[int, float], Dict[int, Optional[int]]]:
    """
    Compute shortest paths from source to all reachable vertices.
    
    Returns:
        distances: Dict mapping vertex to shortest distance from source
        predecessors: Dict mapping vertex to previous vertex in shortest path
    """
    distances: Dict[int, float] = {v: math.inf for v in graph.vertices}
    predecessors: Dict[int, Optional[int]] = {v: None for v in graph.vertices}
    distances[source] = 0
    
    # Priority queue: (distance, vertex)
    pq: List[Tuple[float, int]] = [(0, source)]
    visited: Set[int] = set()
    
    while pq:
        current_dist, u = heapq.heappop(pq)
        
        if u in visited:
            continue
        visited.add(u)
        
        for v, weight in graph.neighbors(u):
            if v in visited:
                continue
            
            new_dist = current_dist + weight
            if new_dist < distances[v]:
                distances[v] = new_dist
                predecessors[v] = u
                heapq.heappush(pq, (new_dist, v))
    
    return distances, predecessors


def reconstruct_path(
    predecessors: Dict[int, Optional[int]], 
    source: int, 
    target: int
) -> Optional[List[int]]:
    """Reconstruct the shortest path from source to target."""
    if predecessors.get(target) is None and target != source:
        return None  # No path exists
    
    path = []
    current = target
    while current is not None:
        path.append(current)
        current = predecessors[current]
    
    return path[::-1]

Bellman-Ford Algorithm handles negative edge weights and detects negative cycles. It relaxes all edges V-1 times, achieving O(VE) complexity. Use it when negative weights exist or when you need cycle detection.

def bellman_ford(
    graph: WeightedGraph, 
    source: int
) -> Tuple[Optional[Dict[int, float]], Dict[int, Optional[int]]]:
    """
    Compute shortest paths handling negative weights.
    
    Returns:
        distances: Dict of shortest distances, or None if negative cycle exists
        predecessors: Dict for path reconstruction
    """
    distances: Dict[int, float] = {v: math.inf for v in graph.vertices}
    predecessors: Dict[int, Optional[int]] = {v: None for v in graph.vertices}
    distances[source] = 0
    
    # Relax all edges V-1 times
    for _ in range(graph.num_vertices - 1):
        for u, v, weight in graph.edges():
            if distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight
                predecessors[v] = u
            # Handle undirected graphs
            if not graph.directed and distances[v] + weight < distances[u]:
                distances[u] = distances[v] + weight
                predecessors[u] = v
    
    # Check for negative cycles
    for u, v, weight in graph.edges():
        if distances[u] + weight < distances[v]:
            return None, predecessors  # Negative cycle detected
    
    return distances, predecessors

Decision guide: Use Dijkstra’s unless you have negative weights. If you’re modeling costs that can be negative (refunds, energy recovery), reach for Bellman-Ford.

Minimum Spanning Tree

A minimum spanning tree (MST) connects all vertices with the minimum total edge weight, using exactly V-1 edges. MSTs solve network design problems: minimum cable to connect buildings, cheapest pipeline network, or most efficient road system.

Kruskal’s Algorithm sorts edges by weight and greedily adds them if they don’t create a cycle. Union-Find makes cycle detection efficient.

class UnionFind:
    """Disjoint set data structure with path compression and union by rank."""
    
    def __init__(self, vertices: Set[int]):
        self.parent = {v: v for v in vertices}
        self.rank = {v: 0 for v in vertices}
    
    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]
    
    def union(self, x: int, y: int) -> bool:
        """Unite sets containing x and y. Returns False if already united."""
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return False
        
        # Union by rank
        if self.rank[root_x] < self.rank[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_y] = root_x
        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1
        return True


def kruskal_mst(graph: WeightedGraph) -> List[Tuple[int, int, float]]:
    """
    Compute minimum spanning tree using Kruskal's algorithm.
    
    Returns:
        List of edges (u, v, weight) in the MST
    """
    # Sort edges by weight
    edges = sorted(graph.edges(), key=lambda e: e[2])
    
    uf = UnionFind(graph.vertices)
    mst: List[Tuple[int, int, float]] = []
    
    for u, v, weight in edges:
        if uf.union(u, v):
            mst.append((u, v, weight))
            if len(mst) == graph.num_vertices - 1:
                break
    
    return mst

Kruskal’s runs in O(E log E) time, dominated by the sort. For dense graphs where E approaches V², Prim’s algorithm with a Fibonacci heap achieves O(E + V log V), but Kruskal’s simplicity wins for most practical cases.

Practical Applications

Let’s build a simple route planner that finds the cheapest path between cities:

def build_route_network() -> WeightedGraph:
    """Build a sample transportation network with costs."""
    network = WeightedGraph(directed=False)
    
    # (city_a, city_b, cost_in_dollars)
    routes = [
        (0, 1, 120),  # NYC -> Boston
        (0, 2, 150),  # NYC -> Philadelphia
        (1, 3, 200),  # Boston -> Chicago
        (2, 3, 180),  # Philadelphia -> Chicago
        (2, 4, 90),   # Philadelphia -> Washington
        (3, 5, 160),  # Chicago -> Denver
        (4, 5, 220),  # Washington -> Denver
        (5, 6, 140),  # Denver -> LA
    ]
    
    for u, v, cost in routes:
        network.add_edge(u, v, cost)
    
    return network


def find_cheapest_route(
    network: WeightedGraph, 
    origin: int, 
    destination: int,
    city_names: Dict[int, str]
) -> None:
    """Find and display the cheapest route between cities."""
    distances, predecessors = dijkstra(network, origin)
    path = reconstruct_path(predecessors, origin, destination)
    
    if path is None:
        print(f"No route from {city_names[origin]} to {city_names[destination]}")
        return
    
    print(f"Cheapest route: {' -> '.join(city_names[v] for v in path)}")
    print(f"Total cost: ${distances[destination]:.0f}")


# Usage
city_names = {
    0: "NYC", 1: "Boston", 2: "Philadelphia",
    3: "Chicago", 4: "Washington", 5: "Denver", 6: "LA"
}

network = build_route_network()
find_cheapest_route(network, 0, 6, city_names)
# Output: Cheapest route: NYC -> Philadelphia -> Chicago -> Denver -> LA
# Total cost: $630

Performance Considerations

Algorithm	Time Complexity	Space Complexity	Best For
Dijkstra (binary heap)	O((V + E) log V)	O(V)	Non-negative weights
Bellman-Ford	O(VE)	O(V)	Negative weights, cycle detection
Kruskal’s MST	O(E log E)	O(V)	Sparse graphs
Prim’s MST	O(E + V log V)*	O(V)	Dense graphs

*With Fibonacci heap

Tips for large-scale graphs:

Use adjacency lists for graphs with less than 10% edge density
Consider lazy deletion instead of removing vertices—mark them invalid
Bidirectional Dijkstra cuts search space roughly in half for point-to-point queries
A search* with admissible heuristics outperforms Dijkstra when you have geometric information
Precompute for repeated queries—contraction hierarchies enable microsecond shortest-path queries on continental road networks

Weighted graphs are foundational. Master these implementations, understand the trade-offs, and you’ll have the tools to tackle optimization problems across domains.