1
$\begingroup$

While the shortest path can be calculated with $O(V+E)$ time over a weighted directed acyclic graph using topological sort, I wonder about the running time of the following BFS type algorithm I thought of.

BFS_requeue(v):
Initialization()
push(s) //push the source node
while the queue contains at least one vertex:
    u = pull()
    for all edges u -> v
        w = edge_weight(u,v)
        if dist(v) > dist(u) + w
            dist(v) = dist(u) + w
            pred(v) = u
            push(v)

Compare one of the standard BFS algorithms, this does not mark vertices, and one vertex can be pushed into the queue more than once. Although it seems that popping a vertex more than once can result in a slower running time in general, I am not sure with the exact running time of the algorithm on a (possibly negative) weighted directed acyclic graph.

Although I suspect in the worst case, this runs like Bellman-ford, in $O(VE)$ time, I cannot think of a concrete example. All the examples I thought of run in $O(V+E)$ time. So what is the running time of this algorithm on a weighted DAG?

I think regardless of the running time, this does identify the shortest path, essentially by relaxing all edges. However, I might be incorrect.

This algorithm is taken from page 7 of chapter 8 of Jeff Erickson's textbook on algorithms. I have only modified the algorithm so it applies to weighted graphs. Nonetheless, this problem is specifically about DAG, rather than weighted graphs in general

Improve this question
$\endgroup$
5
  • $\begingroup$ Can the queue contain a single vertex more than once, or if the vertex v is already in the queue, does push(v) do nothing? $\endgroup$ Commented Dec 26, 2023 at 2:09
  • $\begingroup$ No need to use "Edit:" - instead, revise the question so it reads well for someone who encounters it for the first time. See cs.meta.stackexchange.com/q/657/755. $\endgroup$ Commented Dec 26, 2023 at 2:09
  • $\begingroup$ @D.W. I copied this from Jeff Erickson's textbook, only modifying the weights from unweighted to weighted. I probably should've cited him. In this case, I'm not completely sure, but I think if the vertex v is already in the queue, it still pushes in. Does it matter anyway though? Thank you for sharing the link about editing, I'll be careful in the future. $\endgroup$ Commented Dec 26, 2023 at 3:16
  • $\begingroup$ I encourage you to edit your post to provide a full citation to the original source of the problem. $\endgroup$ Commented Dec 26, 2023 at 3:18
  • $\begingroup$ @D.W. I have added the source for the algorithms. I guess the source of this problem is that it pops up in my brain while learning the material. $\endgroup$ Commented Dec 26, 2023 at 3:24

1 Answer 1

Reset to default
1
$\begingroup$

The running time can be exponential, so it is much worse than $O(|V|+|E|)$ or $O(|V| \cdot |E|)$.

Here is an explicit counterexample. Suppose you have a dag with $n$ vertices, numbered $1,2,\dots,n$, and there is an edge $i \to j$ for each $i,j$ with $i > j$, with weight $2^{i-j}-1$. Suppose that the for-loop traverses the neighbors from lowest-numbered vertex to highest-number vertex. The algorithm will start by visiting vertex $n$, then pushing $1,2,\dots,n-1$ onto the queue, visit vertex $1$, then $2,1$, and so forth. In particular, the condition dist(v) > dist(u) + w will always hold true, so the then-branch of the if-statement will always be executed.

What's the running time, on this graph, with this visit order? It satisfies the recurrence relation

$$T(n) = T(1) + T(2) + T(3) + \dots + T(n-1),$$

which solves to $T(n) = 2^n$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Sorry I'm a little confused, in this case, there are $\Theta(n^{2})$ edges, so $\Theta(n^2) = \Theta(V+E)$? I felt that that $Theta(V+E)$ also works. $\endgroup$ Commented Dec 26, 2023 at 3:12
  • $\begingroup$ @wsz_fantasy, you are right. My analysis was wrong. I have revised my answer, and I think it is now correct. Please do check it for yourself and see whether it seems right to you. $\endgroup$ Commented Dec 26, 2023 at 3:26
  • $\begingroup$ Thank you for the answer, could you please also include the edge weights in this counterexample? $\endgroup$ Commented Dec 26, 2023 at 3:38
  • $\begingroup$ @wsz_fantasy, Ahh, good point! I've included edge weights now. $\endgroup$ Commented Dec 26, 2023 at 4:42

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.