Weighted Graph

A weighted graph attaches a cost, distance, time, capacity, or score to each edge.

Weights matter because the best path may no longer be the path with the fewest edges.

Core Idea

In an unweighted graph, moving across one edge has the same cost as moving across any other edge. In a weighted graph, different edges can have different costs.

This changes which algorithms are valid. BFS gives shortest paths by edge count, but weighted shortest paths usually need different tools.

Representation Contract

A weighted adjacency list stores each edge as (neighbor, weight).

The weight must mean the quantity the algorithm is optimizing, such as cost, time, distance, or risk. Before choosing a shortest-path algorithm, check whether weights are all equal, non-negative, negative, or irrelevant.

Python Example

graph = {
    "A": [("B", 5), ("C", 2)],
    "B": [("D", 1)],
    "C": [("D", 10)],
    "D": [],
}

Each neighbor is stored with the edge weight needed to reach it.

Why Weights Matter

In an unweighted graph, a path with fewer edges is always cheaper because every edge costs the same. In a weighted graph, a path with more edges can be cheaper if those edges have lower weights.

For example:

A -> B costs 100
A -> C costs 1
C -> B costs 1

The path A -> C -> B uses two edges but costs only 2, so it is better than the one-edge path A -> B.

Storing Weights

A common Python adjacency list stores (neighbor, weight) pairs:

for neighbor, weight in graph[node]:
    new_cost = cost_so_far + weight

The traversal must carry cost information, not only visited order.

Algorithm Consequences

If all weights are equal, BFS can solve shortest paths. If weights are non-negative, Dijkstra’s algorithm is often appropriate. If negative weights exist, Bellman-Ford or DAG-specific methods may be needed depending on graph structure.

Common Confusions

Weight does not always mean distance. It can mean cost, time, risk, probability penalty, or any numeric value defined by the problem.

Negative weights require special care. Some shortest path algorithms assume all weights are non-negative.

Another common mistake is using a normal queue just because the graph looks like a graph traversal problem. Weighted shortest paths usually need cost-based processing.

When To Use It

Use a weighted graph when movement or relationship cost matters. If every move has the same cost, an unweighted graph may be enough.

Before choosing a shortest-path algorithm, check whether weights exist and whether any weight can be negative.

The Main Point

A weighted graph makes cost part of movement. Once weights matter, the best path may not be the path with the fewest edges.