0-1 BFS Distances

Problem

Compute single-source shortest paths when every directed edge weight is 0 or 1, using a deque.

Push relaxation results through the front of the deque for weight 0 and through the back for weight 1. edges is a list of [u, v, w] triples with w in {0, 1}. Return distances from src, using -1 for unreachable nodes.

Hint

Keeps the deque sorted by distance, which Dijkstra achieves with a heap.

Test cases

case 1

in: [5,[[0,1,1],[0,2,0],[2,1,0],[1,3,1],[3,4,1]],0]

expected: [0,0,0,1,2]

case 2

in: [3,[[0,1,1],[1,2,1]],0]

expected: [0,1,2]

case 3

in: [3,[[0,1,0],[1,2,1]],0]

expected: [0,0,1]

case 4

in: [3,[[0,1,1]],0]

expected: [0,1,-1]

Starter codePython

from collections import deque
def zero_one_bfs(n, edges, src):
    # Your code here
    pass

4 test cases · run your code against them in the editor