Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Python 0-1 BFS: shortest paths when every edge costs zero or one

Last updated: 30 Sept 20264 min read
tutorial
IntermediateBy AITrove Editorial

0-1 BFS uses a deque to find shortest path costs in a graph whose edge weights are restricted to zero and one.

Download Python source kit

Operation contract

The route graph has four stations. A zero-cost transfer is pushed to the front; a one-cost leg is pushed to the back. The A-to-C-to-B-to-D path uses only zero-cost edges, so its total is zero. The wrapper checks every endpoint and weight before exploring the graph.

Failure and ownership boundary

This is not correct for a weight of two or a negative edge. The deque may retain stale entries after an improvement; comparing the popped cost with the best-known distance avoids processing stale work. Python Dijkstra: nonnegative weights and stale heap entries, Python graph BFS: mark a vertex when it enters the queue and Python Bellman-Ford: negative edges and reachable negative cycles define the neighboring algorithms.

Working program

python
from collections import deque

def transfer_cost(graph, start, goal):
    if type(graph) is not dict or not 1 <= len(graph) <= 30 or start not in graph or goal not in graph:
        raise ValueError("graph boundary")
    if any(type(edges) is not list or len(edges) > 30 or any(type(edge) is not tuple or len(edge) != 2 or edge[0] not in graph or type(edge[1]) is not int or edge[1] not in (0, 1) for edge in edges) for edges in graph.values()):
        raise ValueError("binary weights")
    distances = {start: 0}
    queue = deque([(start, 0)])
    while queue:
        station, cost = queue.popleft()
        if cost != distances[station]:
            continue
        for neighbor, weight in graph[station]:
            next_cost = cost + weight
            if next_cost < distances.get(neighbor, float("inf")):
                distances[neighbor] = next_cost
                if weight == 0:
                    queue.appendleft((neighbor, next_cost))
                else:
                    queue.append((neighbor, next_cost))
    return distances.get(goal)

routes = {"A": [("B", 1), ("C", 0)], "B": [("D", 0)],
          "C": [("B", 0), ("D", 1)], "D": []}
print(transfer_cost(routes, "A", "D"))
try:
    transfer_cost({"A": [("B", 2)], "B": []}, "A", "B")
except ValueError:
    print("weight rejected")

Output

Output
0
weight rejected

Costs and limits

Validation takes O(V+E) time. Under the zero-or-one rule, deque relaxations take O(V+E) time and retain O(V+E) queued state in this implementation; the tiny graph is not a benchmark.

Common Mistakes

  • Use Dijkstra for a general nonnegative weight.
  • Do not accept an undeclared neighbor or silently reinterpret a weight.

Connected lessons

Python Dijkstra: nonnegative weights and stale heap entries, Python graph BFS: mark a vertex when it enters the queue, Python Bellman-Ford: negative edges and reachable negative cycles.

python
zero-one-bfs
Storage details