AOI Study Hub

Appearance

Shortest Paths ​

Written by Haithem Djefel

1. Unweighted Edges ​

Problem Statement: Motivation Problem
Piggyback (USACO)

Definition: Breadth-First Search (BFS)
Used for unweighted graphs. Finds shortest paths in .

text
Algorithm: BFS
Q <- empty queue; dist[v] <- infinity for all v
dist[s] <- 0; Q.enqueue(s)
while Q is not empty:
    u <- Q.dequeue()
    for each neighbor v of u:
        if dist[v] == infinity:
            dist[v] <- dist[u] + 1
            Q.enqueue(v)

Example using BFS

Layer Property: BFS processes the graph in discrete layers , where contains all nodes at distance exactly from the source. It exhaustively explores all nodes in before moving to any node in .

Proof sketch: Assume all vertices at distance are reached via their shortest path. Since BFS explores all neighbors of these vertices before moving to distance , any vertex at distance will be discovered through a vertex at distance . By induction, the first path found to any vertex is the shortest.

Note on Multi-Source: In the case of having multiple source nodes, we do not need to run BFS multiple times. We simply initialize for all starting nodes and push them all into the initial Queue. The algorithm will naturally find the shortest distance from the nearest source to every other node in a single pass.

2. 0 - 1 Weighted Edges ​

Problem Statement: Motivation Problem
Tracks in the Snow (Baltic OI)

Definition: 0-1 BFS
Used when weights are only or . Uses a Deque in .

text
Algorithm: 0-1 BFS
D <- empty deque; dist[v] <- infinity; dist[s] <- 0
D.push_back(s)
while D is not empty:
    u <- D.pop_front()
    for each neighbor v of u with weight w:
        if dist[v] > dist[u] + w:
            dist[v] <- dist[u] + w
            if w == 0:
                D.push_front(v)
            else:
                D.push_back(v)

3. Weighted Edges (Non-Negative) ​

Problem Statement: Motivation Problem
Flight Discount (CSES)

Definition: Dijkstra's Algorithm
Greedy approach for non-negative weights. .

text
Algorithm: Dijkstra
PQ <- priority queue; dist[v] <- infinity; dist[s] <- 0
PQ.push({0, s})
while PQ is not empty:
    {d, u} <- PQ.pop_min()
    if d > dist[u]:
        continue
    for each neighbor v of u with weight w:
        if dist[u] + w < dist[v]:
            dist[v] <- dist[u] + w
            PQ.push({dist[v], v})

Intuition: Dijkstra can be viewed as a generalization of BFS. If all weights were integers, we could replace each edge with unit-length edges and run BFS. The Priority Queue in Dijkstra effectively simulates this by always jumping to the next closest "real" vertex.

Example using Dijkstra

4. Space State Graphs ​

Sometimes a problem does not mention a graph, but can be solved as one by defining a State-Space Graph.

Definition: State-Space Representation

  • Nodes: Each node represents a unique state of the problem (e.g., your current position, the amount of fuel left, and which items you have collected).
  • Edges: An edge exists between two states if you can move from one to the other in a single step/action.
  • Weights: The "cost" of taking that action (time, distance, or fuel).

Common Bijection Examples:

  • Grid Problems: A cell is a node. Edges exist to and .
  • Dijkstra with "States": If you can perform a special move (like "skipping" an edge) up to times, your state is , representing: "I am at node and I have skips remaining."
  • BFS on Numbers: If you can multiply a number by 2 or subtract 1 to reach a target, each number is a node, and the operations are edges.

At first it is quite hard and unintuitive to come up with such ideas, as it requires creativity and being familiar with this type of problems, but at the same time this technique is very powerful, as sometimes the problem may seem impossible to approach, but once bijected onto the right graph, becomes a simple shortest path problem, we will see a demonstration with the following example:

Problem: The Two Buttons Puzzle
You are given two integers and . Your goal is to reach starting from using the minimum number of operations. You have two buttons:

  • Red Button: Multiplies the current number by 2 ().
  • Blue Button: Subtracts 1 from the current number ().

Find the minimum number of "clicks" required.

The Shortest Path Bijection
State Space: Each integer represents a node in a graph.
Transitions:

  1. An edge from to with weight 1.
  2. An edge from to with weight 1.

Observation: Since all weights are equal, this is a shortest path problem on an implicit graph. We solve it by running BFS starting at and stopping as soon as we reach .

5. Problemset ​

Problems are sorted in ascending order of their difficulty.

Practice Problems ​

Level:

Level:

Level: