Modeling Problems as Weighted Graphs

Plenty of graph problems never say "graph". They give you equations, one-way roads, circles on a plane or a combination lock. The hard part is the modeling: deciding what a node is, what an edge is, which way it points and what it weighs. Once that's settled, a plain BFS, DFS or Dijkstra does the rest.

The idea#

The modeling comes down to four questions. Answer them before you write any traversal.

Nodes: what are the things? Variables, cities, bombs, grid cells, whole puzzle states.
Edges: which pairs are related? Given directly, derived from geometry, or "one move apart".
Direction: does "a relates to b" imply "b relates to a"? If not, the graph is directed.
Weight: what does crossing an edge cost or carry? A ratio, a 0/1 flag, a distance.

How to spot it#

A few input shapes hide a graph again and again. This table maps each one to its model, using the four questions above.

You see...	Model it as
`a / b = 2.0` style equations	Weighted directed edges, `a → b` and `b → a`
One-way roads that you may have to reverse	Undirected traversal with a 0/1 cost per edge
Circles, ranges or "can reach" by distance	Directed edges built by comparing every pair
Points to connect at minimum total cost	A complete graph with distance weights, then an MST
"Must be in different groups"	An edge per conflict, then a 2-color check
A lock, board or bitmask that changes by single moves	A node per state, an edge per move

Template#

Once the model is set, most of these problems are one traversal that carries a value along the path: a product, a sum of flags, a step count. Build the edges from the model, including any reverse edge, then walk.

for each relation in the input:
    add edge a -> b with its weight
    if the relation also holds backwards:
        add edge b -> a with its reverse weight
queue = [(source, start value)]; seen = {source}
while queue is not empty:
    node, acc = pop from the front of queue
    if node is the target: return acc
    for each (nei, w) next to node:
        if nei not in seen:
            add nei to seen
            push (nei, combine(acc, w))  # multiply, add, count
return the "not found" value

Pitfalls#

These are the mistakes that most often cost a correct answer.

Giving a reverse edge the same weight when the relation inverts.
Treating an asymmetric relation as undirected.
Using sqrt for distance comparisons instead of comparing squares.
Forgetting inputs that name a node the graph has never seen.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with Evaluate Division.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Evaluate Division

Each equation a / b = v becomes an edge a → b with weight v and a reverse edge b → a with weight 1 / v. A query x / y is the product of the weights along any path from x to y. The equations are consistent, so any path gives the same product and plain BFS is enough. A query on a variable that never appears returns -1.0.

Hint: Reorder Routes to Make All Paths Lead to the City Zero

Direction becomes a cost. Store each road a → b twice: as (b, 1) in the list of a (using it from a means reversing it) and as (a, 0) in the list of b (it already points the right way). BFS from 0 over this undirected view and add up the flags on the edges you take.

Hint: Detonate the Maximum Bombs

Bomb i sets off bomb j when the squared distance between their centers is at most $r_i^2$ ; comparing squares avoids sqrt and floating-point error. The relation uses only $r_i$ , so it is directed. Run a DFS from every bomb.

Hint: Open the Lock

A node is a 4-digit combination, and each turn of one wheel is an edge. BFS gives the fewest turns.

Hint: Shortest Path Visiting All Nodes

The node alone is not enough state. Make the state (node, mask of visited nodes) and run BFS over those pairs.

Hint: Knight Dialer

The graph is small: the knight moves on a keypad. Count with DP over that graph rather than a search; see Grid & Path DP.

Hint: Min Cost to Connect All Points (variation)

Every pair of points is an edge weighted by Manhattan distance. That turns the problem into a Minimum Spanning Tree.

Hint: Find the Safest Path in a Grid (variation)

Each cell's weight is its distance to the nearest thief, computed by multi-source BFS. The path search then runs over those weights, as in Bottleneck / Minimax Paths.

Hint: Relations as groups (variation)

When the relation is an equivalence ("a == b", "same email", "same row"), you need groups, not paths. Use Union-Find. "Must be apart" relations become edges for a bipartite check.

Key takeaways#

Decide nodes, edges, direction and weight before choosing an algorithm.
Ratios become a pair of edges, v and 1/v; answers multiply along a path.
A 0/1 weight can record "this edge points the wrong way".
Check whether a relation is symmetric before adding both directions.
When states change by single moves, each state is a node and BFS finds the fewest moves.

Core idea#

Many graph problems never say "graph". The hard part is the modeling. Once nodes, edges, direction and weight are clear, a plain BFS, DFS or Dijkstra solves the problem.

Key points#

Nodes: variables, cities, bombs, cells or whole puzzle states.
Edges: given directly, derived from geometry, or "one move apart".
Direction: if "a relates to b" does not imply the reverse, the graph is directed.
Weight: a ratio, a 0/1 flag or a distance.
Evaluate Division: a / b = v gives a → b with v and b → a with 1 / v. A query multiplies weights along a path.
Reorder Routes: store road a → b as (b, 1) in a's list and (a, 0) in b's list. BFS from 0 and sum the flags.
Bombs: compare squared distance with $r_i^2$ . The relation is directed.

Model it as#

You see	Model it as
`a / b = 2.0` equations	Weighted directed edges both ways
One-way roads you may reverse	Undirected traversal with a 0/1 cost
Points to connect cheaply	Complete graph, then MST
"Must be in different groups"	Conflict edges, then a 2-color check
A lock or board that changes by single moves	A node per state, BFS
`a == b`, same email, same row	Union-Find groups

Template#

for each relation (a, b, w):
    add edge a -> b with weight w
    if it holds backwards: add b -> a with the reverse weight
queue = [(source, start value)]; seen = {source}
while queue is not empty:
    node, acc = pop from the front of queue
    if node is the target: return acc
    for each (nei, w) next to node, not in seen:
        add nei to seen
        push (nei, combine(acc, w))    # multiply, add, count
return the "not found" value

Pitfalls#

A reverse edge with the same weight instead of 1 / v.
Treating an asymmetric relation as undirected.
Using sqrt instead of comparing squares.
Returning anything but -1.0 for an unknown variable.

Say it in an interview#

"First decide what a node, an edge, its direction and its weight are."
"The equations are consistent, so any path gives the same product and BFS is enough."