0
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thank you! I didn't know about the priority queue idea. I also found out about the "0-1 breadth-first search" algorithm, do you think there's a reason to prioritise one over the other of these two? $\endgroup$
    – Anna
    Feb 21, 2023 at 17:18
  • $\begingroup$ 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. $\endgroup$
    – Steven
    Feb 21, 2023 at 17:26
  • $\begingroup$ Thank you for the insights! $\endgroup$
    – Anna
    Feb 21, 2023 at 17:27
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Steven
    Feb 21, 2023 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.