Weighted Graph Representation: From Basics to Advanced Operations

1. Introduction and Core Concepts

Weighted graph representation is the foundational technique for modeling relationships where connections between entities carry a cost, distance, capacity, or strength. While an unweighted graph only captures whether two vertices are connected, a weighted graph representation encodes how they are connected through a numerical weight assigned to each edge. This additional dimension transforms a simple topological structure into a powerful model for optimization, routing, and decision-making problems.

Formally, a weighted graph is defined as G = (V, E, w) where V is a set of vertices, E is a set of edges, and w: E → R is a weight function that maps each edge to a real number. Weights can be positive, negative, or zero depending on the domain, and they may represent physical distance, travel time, monetary cost, bandwidth, probability, or similarity. The choice of weighted graph representation — how this structure is stored in memory — directly impacts the efficiency of every algorithm that operates on it, from shortest path finding to network flow analysis.

Understanding weighted graph representation matters because real-world systems are rarely uniform. In a road network, the edge between two intersections is not just a connection but a road segment with a length and expected travel time. In a social network, an edge might have a strength score based on interaction frequency. In cloud infrastructure, links between servers have latency and throughput. Without an efficient representation that preserves and provides fast access to these weights, algorithms like Dijkstra, Bellman-Ford, Floyd-Warshall, and Prim's Minimum Spanning Tree would be impractical at scale. The representation you choose determines memory footprint, cache locality, and the time complexity of core operations such as edge lookup, neighbor traversal, and weight updates.

Why Weighted Representation Differs from Unweighted

In an unweighted graph, an adjacency matrix can store a simple boolean, and an adjacency list can store a list of neighbor IDs. For a weighted graph representation, each entry must store a tuple of (neighbor, weight) or a numeric value where absence is distinguished from a zero-weight edge. This subtle difference introduces design decisions around sentinel values, handling of disconnected vertices, and support for parallel edges with different weights. For instance, using 0 to denote no edge fails if 0 is a valid weight, requiring the use of infinity or None as a sentinel.

Another core concept is the distinction between directed and undirected weighted graphs. In an undirected weighted graph, the edge (u, v, w) implies both (u, v) and (v, u) share the same weight, requiring symmetric storage. In a directed weighted graph, w(u, v) may differ from w(v, u) or one direction may not exist at all. A robust weighted graph representation must handle both cases cleanly while avoiding duplication errors and supporting efficient transpose or reverse-graph operations needed for algorithms like Kosaraju's or Johnson's.

2. How It Works

At its core, a weighted graph representation extends classic graph storage structures by associating a scalar value with each adjacency. There are three canonical mechanisms: the adjacency matrix, the adjacency list, and the edge list. Each encodes the same mathematical object but organizes the weight information differently for trade-offs in access patterns.

The weighted adjacency matrix is a |V| x |V| two-dimensional array W where W[i][j] = weight of edge (i, j) if the edge exists, and a sentinel value such as infinity otherwise. The diagonal is typically 0 for distance graphs or infinity for strictly edge-weighted semantics. This representation provides O(1) edge weight lookup and is naturally suited for dense graphs and matrix-based algorithms like Floyd-Warshall. However, it consumes O(V²) space regardless of edge count, making it wasteful for sparse graphs with millions of vertices but relatively few connections.

The weighted adjacency list stores for each vertex a list of pairs (neighbor, weight). Conceptually it is an array or dictionary mapping vertex → list of outgoing edges. This is the most common weighted graph representation for sparse graphs because its space is O(V + E) and it allows efficient iteration over a vertex's neighbors. Edge existence checks require scanning the neighbor list, which is O(degree(v)), but traversal of all edges is linear in the graph size. Most modern graph libraries, including NetworkX and adjacency structures used in web-scale crawlers, default to this form.

The Edge List and Compressed Variants

The edge list representation stores a flat collection of triples (u, v, w) for every edge. It is the simplest to serialize, sort, and stream, and it is the input format for Kruskal's Minimum Spanning Tree algorithm and Bellman-Ford. While it is inefficient for neighbor queries — requiring a full scan to find adjacent vertices — it excels when the primary operation is iterating over all edges in weight order or when the graph is built incrementally from external data sources like CSV files or database tables.

Advanced systems often use compressed or hybrid weighted graph representations. Compressed Sparse Row (CSR) stores adjacency lists in two contiguous arrays: one for column indices and weights, and one for row pointers. This improves cache locality and is used in high-performance graph analytics engines and GPU processing. For dynamic graphs where weights update frequently, such as live traffic routing, an adjacency map using hash tables (dict of dicts) allows O(1) average weight updates and deletions without scanning lists. The choice depends on whether the workload is read-heavy, write-heavy, dense, or sparse.

Weight semantics also affect mechanism design. If weights are non-negative, Dijkstra's algorithm with a binary heap is optimal. If negative weights are allowed but no negative cycles exist, Bellman-Ford is required and the representation must efficiently support relaxation over all edges. If weights are integers within a bounded range, Dial's algorithm with bucket queues can achieve near-linear time, but the representation must support bucket indexing. Understanding these interactions is essential to selecting the right weighted graph representation for a given algorithmic pipeline.

3. Implementation

Implementing a weighted graph representation in Python requires balancing clarity, performance, and flexibility. Python's dictionaries and lists make it easy to build adjacency lists, while NumPy or nested lists can emulate adjacency matrices for dense graphs. Below are production-ready patterns with detailed comments covering the four most practical approaches.

The first implementation shows a weighted adjacency matrix using nested lists and an infinity sentinel. This approach is ideal for small, dense graphs and for teaching Floyd-Warshall where matrix operations are natural. Note the use of float('inf') to distinguish missing edges from zero-weight edges.

# Weighted Adjacency Matrix Implementation
INF = float('inf')

def create_weighted_matrix(num_vertices):
    """Create VxV matrix initialized with INF (no edge) and 0 on diagonal."""
    matrix = [[INF] * num_vertices for _ in range(num_vertices)]
    for i in range(num_vertices):
        matrix[i][i] = 0  # Distance to self is zero
    return matrix

def add_weighted_edge_matrix(matrix, u, v, weight, directed=False):
    """Add weighted edge to matrix. Handles directed vs undirected."""
    matrix[u][v] = weight
    if not directed:
        matrix[v][u] = weight  # Symmetric for undirected

# Example: 4-vertex undirected graph
W = create_weighted_matrix(4)
add_weighted_edge_matrix(W, 0, 1, 4)
add_weighted_edge_matrix(W, 0, 2, 2)
add_weighted_edge_matrix(W, 1, 2, 1)
add_weighted_edge_matrix(W, 1, 3, 5)
add_weighted_edge_matrix(W, 2, 3, 8)

def get_weight_matrix(matrix, u, v):
    """O(1) weight lookup. Returns INF if no edge."""
    return matrix[u][v]

The second implementation is the most widely used weighted graph representation: an adjacency list using a dictionary of lists. It supports both string-labeled vertices and integer IDs, handles directed and undirected graphs, and allows multiple edges to be filtered or retained. Weight updates are performed by scanning the neighbor list, which is efficient when average degree is low.

# Weighted Adjacency List using dict of list of tuples
from collections import defaultdict

class WeightedGraphList:
    def __init__(self, directed=False):
        self.graph = defaultdict(list)
        self.directed = directed

    def add_edge(self, u, v, weight):
        """Add (neighbor, weight) tuple. O(1) insertion."""
        # Remove existing edge if present to allow weight update
        self.graph[u] = [(n, w) for n, w in self.graph[u] if n != v]
        self.graph[u].append((v, weight))
        if not self.directed:
            self.graph[v] = [(n, w) for n, w in self.graph[v] if n != u]
            self.graph[v].append((u, weight))
        # Ensure vertices exist even if isolated
        if v not in self.graph:
            self.graph[v] = self.graph[v]

    def get_neighbors(self, u):
        """Return list of (neighbor, weight). O(1) to access, O(degree) to iterate."""
        return self.graph.get(u, [])

    def get_weight(self, u, v):
        """Find weight of edge (u, v). O(degree(u)) scan."""
        for neighbor, w in self.graph.get(u, []):
            if neighbor == v:
                return w
        return None  # No edge

# Usage
g = WeightedGraphList(directed=False)
g.add_edge('A', 'B', 4)
g.add_edge('A', 'C', 2)
g.add_edge('B', 'C', 1)
g.add_edge('B', 'D', 5)
print(g.get_neighbors('B'))  # [('A', 4), ('C', 1), ('D', 5)]

For algorithms that require a priority queue, the adjacency list integrates seamlessly with Dijkstra's algorithm. The following implementation demonstrates how the weighted graph representation enables efficient relaxation. Pay attention to the heap operations and the check that discards stale entries, which is critical when the graph is represented as adjacency lists.

# Dijkstra's Algorithm on Weighted Adjacency List
import heapq

def dijkstra_weighted(graph, start):
    """
    Compute shortest paths from start using weighted adjacency list.
    graph: dict {u: [(v, weight), ...]}
    Returns dict of shortest distances.
    """
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    heap = [(0, start)]  # (distance, vertex)
    visited = set()

    while heap:
        d, u = heapq.heappop(heap)
        if u in visited:
            continue
        if d > dist[u]:  # Stale entry check
            continue
        visited.add(u)
        for v, w in graph.get(u, []):
            # Relaxation step: check if new path is shorter
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist

# Example run
example_graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('C', 1), ('D', 5)],
    'C': [('A', 2), ('B', 1), ('D', 8)],
    'D': [('B', 5), ('C', 8)]
}
print(dijkstra_weighted(example_graph, 'A'))  # {'A': 0, 'B': 3, 'C': 2, 'D': 8}

The final implementation shows the weighted edge list and Floyd-Warshall using a matrix. Edge lists are trivial to sort by weight for Kruskal's algorithm and to iterate for Bellman-Ford. Floyd-Warshall demonstrates how a matrix-based weighted graph representation naturally supports all-pairs shortest paths via dynamic programming.

# Weighted Edge List and Floyd-Warshall (All-Pairs Shortest Path)
def floyd_warshall_weighted(matrix):
    """
    All-pairs shortest path on weighted adjacency matrix.
    matrix[i][j] = weight or INF if no edge.
    Returns distance matrix with shortest path weights.
    """
    n = len(matrix)
    # Copy matrix to avoid mutating input
    dist = [row[:] for row in matrix]

    for k in range(n):
        for i in range(n):
            for j in range(n):
                # If path via k is shorter, update
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

# Edge list representation: list of (u, v, weight)
edge_list = [
    (0, 1, 4),
    (0, 2, 2),
    (1, 2, 1),
    (1, 3, 5),
    (2, 3, 8)
]

# Sort edge list by weight - useful for Kruskal's MST
edge_list_sorted = sorted(edge_list, key=lambda x: x[2])
print(edge_list_sorted)  # [(1, 2, 1), (0, 2, 2), (0, 1, 4), ...]

# For Bellman-Ford, simply iterate edge_list to relax all edges V-1 times
def bellman_ford_edge_list(vertices, edge_list, source):
    dist = {v: float('inf') for v in vertices}
    dist[source] = 0
    for _ in range(len(vertices) - 1):
        for u, v, w in edge_list:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist

4. Step-by-Step Example

Consider a concrete weighted graph representing a regional delivery network with four hubs: A, B, C, and D. The edges and weights (delivery time in hours) are: A-B = 4, A-C = 2, B-C = 1, B-D = 5, C-D = 8. This small graph illustrates how different weighted graph representations store the same information and how an algorithm traverses it.

Step 1: Build the representations. As an adjacency matrix with order [A, B, C, D], the matrix W is: Row A: [0, 4, 2, INF], Row B: [4, 0, 1, 5], Row C: [2, 1, 0, 8], Row D: [INF, 5, 8, 0]. As an adjacency list: A → [(B,4), (C,2)], B → [(A,4), (C,1), (D,5)], C → [(A,2), (B,1), (D,8)], D → [(B,5), (C,8)]. As an edge list: [(A,B,4), (A,C,2), (B,C,1), (B,D,5), (C,D,8)]. All three encode identical topology and weights but offer different query patterns.

Step 2: Execute Dijkstra's algorithm from source A using the adjacency list. Initialization sets dist[A]=0, dist[B]=dist[C]=dist[D]=INF, heap=[(0,A)]. Pop (0,A): relax neighbors B and C. dist[B] becomes 4, dist[C] becomes 2, heap becomes [(2,C), (4,B)]. Pop (2,C): from C, examine B with weight 1. The alternative path A→C→B has cost 2+1=3, which is < current dist[B]=4, so dist[B] updates to 3 and heap becomes [(3,B), (4,B), (8,D) after processing C→D]. Note that the heap now contains a stale entry (4,B) that will be ignored later.

Step 3: Continue traversal. Pop (3,B): from B, examine D with weight 5. Path A→C→B→D costs 3+5=8, which equals current dist[D]=10? Actually dist[D] was set to 10 via C→D (2+8). The new path 8 is better, so dist[D] updates to 8. Heap becomes [(4,B stale), (8,D), (10,D stale)]. Pop (4,B) is skipped because visited contains B and d > dist[B]. Pop (8,D): D has no unvisited neighbors that improve distances. Algorithm terminates with final distances: A=0, C=2, B=3, D=8. The shortest path to D is A→C→B→D, not the direct-looking A→C→D, demonstrating why weight-aware traversal is essential.

Step 4: Interpret results across representations. If we had used the matrix, the same relaxation would involve scanning entire rows to find neighbors, checking INF sentinels. With the edge list, Dijkstra would be inefficient because finding neighbors of C requires scanning all five edges. This walkthrough highlights why adjacency lists are preferred for single-source shortest paths on sparse graphs, while matrices shine for dense graphs and all-pairs computations where every pair must be considered anyway.

5. Complexity Analysis

The performance of any weighted graph representation is measured by time to perform core operations and memory consumption. The choice between matrix, list, and edge list is not merely stylistic; it determines whether an algorithm runs in seconds or fails to fit in memory on large datasets such as web graphs with billions of edges.

For a graph with V vertices and E edges, the weighted adjacency matrix uses Θ(V²) space always, storing a weight for every possible pair. This is optimal for dense graphs where E approaches V², but wasteful for sparse graphs where E ≪ V². For example, a social network with 1 million users and average degree 200 would require 1 trillion matrix entries, far beyond feasible memory, while an adjacency list would store only ~200 million entries.

Time complexity varies by operation. Edge weight lookup is O(1) in a matrix but O(degree) in a list. Iterating over all neighbors of a vertex is O(V) in a matrix (must scan full row) but O(degree) in a list. Enumerating all edges is O(V²) in a matrix and O(V+E) in a list. Weight updates are O(1) in a matrix and O(degree) in a list unless a hash map is used. These differences compound in algorithms: Dijkstra with a binary heap runs in O((V+E) log V) on an adjacency list but degrades to O(V²) with a matrix if implemented naively without a heap.

Weight-specific considerations also affect complexity. If weights are integers and bounded by C, a 0-C bucket Dial's implementation can achieve O(E + C·V) with an adjacency list. For graphs with negative weights, the need to detect negative cycles adds O(V·E) cost regardless of representation, but edge lists make the relaxation loop cache-friendly. When weights are floating-point, precision and comparison stability become concerns, but do not change asymptotic complexity.

6. Variations and Optimizations

Beyond the three canonical forms, several optimized weighted graph representations address specific performance bottlenecks in production systems. One common optimization is the adjacency map or dictionary-of-dictionaries: graph[u][v] = weight. This provides O(1) average weight lookup, update, and deletion via hashing, at the cost of higher memory overhead per edge. It is ideal for dynamic graphs such as live ride-sharing networks where edge weights (ETA) update every few seconds and fast point queries dominate.

For large-scale static graphs, Compressed Sparse Row (CSR) and Compressed Sparse Column (CSC) offer superior cache locality. CSR stores three arrays: row_ptr of size V+1, col_idx of size E, and weights of size E. Traversing neighbors of vertex u involves iterating from row_ptr[u] to row_ptr[u+1] in contiguous memory, which is far more CPU-cache friendly than pointer-chasing through Python lists. Libraries like SciPy, GraphBLAS, and Gunrock use CSR for weighted graph analytics on GPUs and multi-core CPUs.

Another variant is the adjacency set with weight mapping, where each vertex stores a set of neighbors and a parallel dict for weights. This prevents duplicate edges and provides O(1) membership testing, useful when the graph is built from noisy data that may contain parallel edges with conflicting weights. The strategy for handling parallel edges — keep minimum, keep maximum, keep latest, or keep all — should be explicit in the weighted graph representation's API to avoid subtle bugs in shortest path calculations.

Handling Special Weight Types

Optimizations also depend on weight characteristics. For integer weights with small range, an adjacency list can be augmented with bucketed adjacency to support 0-1 BFS or Dial's algorithm. For multi-weighted graphs where each edge has multiple metrics (e.g., distance and cost), the representation can store a tuple or object per edge: (neighbor, distance, cost, latency). This multi-criteria weighted graph representation enables Pareto-optimal path finding but increases memory and requires custom comparators.

For very dense weighted graphs, a hybrid approach can store the matrix as a NumPy array of floats or as a memory-mapped file for graphs that exceed RAM. Using NumPy allows vectorized operations for Floyd-Warshall and fast matrix multiplication for transitive closure. For sparse graphs with frequent weight updates, a copy-on-write or persistent representation may be used to support snapshot isolation in databases, where each version of the graph shares unchanged structure while updated weights are stored differentially.

7. Real-World Applications

Weighted graph representation is not an academic abstraction; it underpins critical infrastructure across web servers, databases, networks, and logistics. The ability to efficiently store and query weighted edges directly translates to lower latency, lower cost, and better user experiences in production systems.

In computer networks and web infrastructure, routers and load balancers model the internet as a weighted graph where vertices are routers or data centers and edge weights are latency, bandwidth, or packet loss. Protocols like OSPF and IS-IS run Dijkstra on a link-state database that is essentially a distributed weighted adjacency list. Content Delivery Networks use weighted graphs to select the optimal edge server for a client, with weights dynamically updated based on real-time health checks. A poor representation that makes weight updates expensive would cause stale routing and degraded performance.

In databases, query optimizers represent join ordering as a weighted graph where tables are vertices and edge weights are estimated join costs or selectivities. Graph databases like Neo4j, Amazon Neptune, and TigerGraph natively store weighted relationships — for example, a KNOWS edge with a strength weight or a ROAD edge with distance — using adjacency list-like structures optimized for traversals. Recommendation engines model user-item interactions as bipartite weighted graphs, where weights are ratings or purchase frequencies, and run personalized PageRank or collaborative filtering that relies on fast neighbor iteration.

In transportation and logistics, weighted graph representation powers every mapping service. Google Maps and OpenStreetMap store road networks as weighted adjacency lists where edge weights combine distance, speed limits, and live traffic. Optimization for last-mile delivery solves Vehicle Routing Problems that repeatedly query and update these weights. In airline scheduling, the graph's vertices are airports and edge weights are flight costs or durations; finding the cheapest itinerary with layovers is a k-shortest paths problem that depends on efficient weight access.

8. Comparison with Alternatives

Choosing a weighted graph representation requires comparing it against both unweighted alternatives and other weighted encodings. The decision hinges on graph density, operation mix, mutability, and memory constraints. An unweighted graph may suffice when all edges are equal, but it cannot model cost-sensitive problems without artificially expanding the graph.

Compared to an unweighted adjacency list that stores only neighbor IDs, a weighted adjacency list adds a weight field per edge, increasing memory by a constant factor but enabling cost-aware algorithms. Compared to an adjacency matrix for unweighted graphs that stores booleans, a weighted matrix stores floats or integers and requires a sentinel for missing edges, complicating initialization. Edge lists for unweighted graphs store pairs (u, v), while weighted edge lists store triples (u, v, w), which is a minimal change but loses fast neighbor lookup.

The most important comparison is among weighted representations themselves. No single structure dominates all workloads. Dense graphs favor matrices, sparse graphs favor lists, and sorting-heavy workloads favor edge lists. Modern systems often maintain multiple representations simultaneously — for example, storing both an adjacency list for traversal and an edge list for sorting — and keep them synchronized, trading memory for speed.

When evaluating alternatives, also consider implicit representations. For grid-based pathfinding in games, the weighted graph is not stored explicitly at all; weights are computed on-the-fly from terrain costs. For complete graphs where every pair has a weight defined by a distance function (e.g., Euclidean TSP), storing the matrix is redundant and weights can be computed lazily. These implicit weighted graph representations save memory but shift cost to computation, which is beneficial when the weight function is cheap to evaluate.

9. Common Mistakes and Best Practices

Even experienced engineers introduce subtle bugs when implementing weighted graph representation. One of the most frequent mistakes is using 0 or -1 as a sentinel for missing edges in an adjacency matrix. If 0 is a valid edge weight — as in zero-cost transfers or free shipping — this conflates absence with a legitimate weight. Best practice is to use float('inf') or None for missing edges and explicitly handle the diagonal. Similarly, initializing distances to a large integer like 10**9 risks overflow when adding weights; using float('inf') ensures that inf + w remains inf.

Another common pitfall is mishandling undirected graphs by adding only one direction or by duplicating weights inconsistently. If add_edge for an undirected graph updates (u, v) but not (v, u), algorithms will see an asymmetric graph and produce incorrect shortest paths. Conversely, storing both directions and then iterating over all edges without deduplication will double-count edges in Kruskal's algorithm. The fix is to encapsulate edge insertion in a single method that enforces symmetry and to document whether edge iteration yields directed or undirected views.

Performance mistakes include using an adjacency matrix for a sparse graph with millions of vertices, leading to out-of-memory errors, and using a Python list scan for weight lookup in a dense graph where a matrix or hash map would be O(1). A related issue is not handling parallel edges: if the input contains multiple edges between the same vertices with different weights, naively appending all of them to an adjacency list will cause Dijkstra to consider redundant paths. Decide upfront whether to keep the minimum weight, keep all edges, or raise an error, and implement deduplication accordingly.

Best Practices for Robust Implementations

• Choose representation by workload: Use adjacency lists for sparse, traversal-heavy workloads; matrices for dense, lookup-heavy workloads; edge lists for sorting-heavy workloads. Profile with realistic V and E.
• Validate weights on insertion: Reject NaN weights, check for negative weights if your algorithm assumes non-negativity, and log warnings for zero-weight cycles that may cause infinite loops in some formulations.
• Use heapq with stale-entry skipping: When running Dijkstra on an adjacency list, do not attempt to decrease-key in the heap; instead push new entries and skip stale ones where d > dist[u]. This keeps the implementation simple and efficient.
• Separate topology from weights: For multi-criteria graphs, store weights as objects or named tuples rather than overloading a single number, making the code self-documenting and extensible.
• Test with disconnected and negative cases: Include unit tests for isolated vertices, self-loops, negative edges, and graphs where the shortest path requires many hops to ensure the representation handles INF propagation correctly.
• Consider immutability for concurrency: In web servers handling concurrent graph queries, use immutable or copy-on-write weighted graph representations to avoid race conditions during weight updates.

10. Interview Questions

Weighted graph representation is a staple of technical interviews for backend, infrastructure, and data engineering roles. Interviewers use it to assess understanding of trade-offs, algorithm integration, and practical implementation. Below are common questions with guidance on what a strong answer includes.

Q1: When would you choose a weighted adjacency matrix over a weighted adjacency list?

A strong answer explains that a matrix is preferred when the graph is dense (E close to V²), when O(1) edge weight lookup is critical, or when implementing all-pairs algorithms like Floyd-Warshall that need to iterate over all vertex pairs anyway. Mention the O(V²) memory cost and give a concrete threshold: if V=10,000, a matrix needs 100M entries, which is ~800MB for 8-byte floats, often infeasible. For sparse graphs like web or social graphs, an adjacency list with O(V+E) memory is superior. Bonus points for mentioning CSR as a compromise that retains cache locality while staying sparse.

Q2: How do you handle negative edge weights in your weighted graph representation, and which algorithms still work?

Explain that the representation itself can store negative weights without change, but algorithm choice is affected. Dijkstra fails with negative weights because it greedily finalizes vertices assuming non-negative extensions. Bellman-Ford works with negative weights (but not negative cycles) and is naturally implemented over an edge list by relaxing all edges V-1 times. Floyd-Warshall also handles negatives. Mention detection of negative cycles by checking for further relaxation after V-1 iterations. Also note that sentinel INF must be handled carefully to avoid overflow when adding negative weights to INF.

Q3: Implement a function to update the weight of an edge (u, v) in a weighted adjacency list. What is its time complexity?

Expected implementation scans the neighbor list of u to find v and replaces the weight, and if undirected, does the same for v's list. Complexity is O(degree(u)) average, O(V) worst case for a star graph. Discuss optimization: using a dict-of-dicts gives O(1) average update at higher memory cost. Provide code that handles edge not found by inserting it, and mention handling parallel edges by updating all occurrences or keeping the minimum. Interviewers look for edge case handling and clear complexity analysis.

Q4: You have a weighted graph with 1 billion vertices and 2 billion edges representing a web graph. How would you store it?

This tests scalability reasoning. Answer: a matrix is impossible (10¹⁸ entries). An adjacency list in Python objects would also exceed memory due to per-object overhead. Use a compressed representation like CSR with 32-bit or 64-bit arrays, store weights as 4-byte floats, and memory-map from disk or distribute across shards. Mention using external storage like SSTables, using adjacency lists partitioned by vertex hash, and using frameworks like GraphX or Gemini. Also discuss that for such scale, you would not store the full graph on a single machine and would use iterative, out-of-core algorithms.

Q5: How does the choice of weighted graph representation affect Dijkstra's time complexity?

Explain that Dijkstra's complexity depends on both the priority queue and the representation. With a binary heap and adjacency list, it is O((V+E) log V) because each edge is relaxed once and each heap operation is logarithmic. With an array-based priority queue and adjacency matrix, it is O(V²) because finding the minimum unvisited vertex scans all V each iteration and neighbor iteration scans full rows. With a Fibonacci heap and adjacency list, it improves to O(E + V log V). Emphasize that using an edge list for Dijkstra would be inefficient because finding neighbors requires O(E) per vertex, leading to O(V·E).

Mastering weighted graph representation means understanding not just how to store weights, but how that storage interacts with algorithms, hardware, and real-world constraints. Whether you are optimizing database joins, routing packets, or answering interview questions, the ability to select and implement the right representation is what separates a working solution from an efficient, production-ready system.