# Which algorithm solves the single-pair shortest path in a weighted directed cyclic graph?

I need to find the shortest path between two nodes in a directed, positively weighted graph that migt contain cycles. All weights are either zero or one. If it was not weighted, I'd use breadth-first search. Dijkstra's algorithm should solve this, but is there a more appropriate algorithm?

Since all distances are between $$0$$ and $$n-1$$, Dijkstra's algorithm with a suitable priority queue takes time $$O(n+m)$$, where $$n$$ and $$m$$ are the number of edges and vertices of the graph, respectively.
The priority queue is simply an array $$A$$ such that $$A[i]$$ contains a list of all elements with key $$i$$. The keys extracted during Dijkstra's algorithm correspond to distances in the graph and are always non-decreasing. Therefore to report the smallest element in the queue it suffices scan the array starting from the previous index $$i$$ (initially $$i=0$$) until an $$A[i]$$ that stores a non-empty list $$L$$ is found. Then remove any element element $$x$$ from $$L$$ and return it.
• The 0-1 breadth first algorithm is essentially the same once you realize that only two buckets of $A$ can be full at any point in time. When a vertex $v$ is extracted from "bucket" $A[i]$, it has distance $i$ from the source. All edges $(v,u)$ relaxed while considering $v$ will yield distances that are either $i$ or $i+1$. This shows that you can just keep the "current" bucket and the "next" bucket. The 0-1-BFS merges both buckets in a single list. If a vertex has distance $i$, it is added at the front of the list (i.e. in the "current") bucket. Otherwise it is appended at the end of the list. Feb 21, 2023 at 17:26
• It might be easier to implement 0-1-BFS since you only deal with a single list, and you don't have to keep track of $i$. Feb 21, 2023 at 17:27