1
$\begingroup$

Let $G=(V,E)$ a directed graph s.t $|V|=n$. Let $w:E \to \mathbb{R}$ a weight function.

Describe an algorithm which finds the minimal-weighted walk of length $\leq n$ from $s \in V$ to all other nodes.

The algorithm must return the walks and not only their respective weights.

So I have an idea, but I'm really not sure if it works. In addition, something about the runtime isn't adding up, but I can't tell what I'm missing (I'll explain after the algorithim).

Algorithim:

  1. Find $G^{*}$ (SCC graph) using DFS

  2. Run SSSP in DAG algorithm from the SCC that contains $s$ on $G^{*}$

  3. $\forall v \in V$:

    3.0. Exists some $C_i$ s.t $v \in C_i$

    3.1. If $v \in C_i$ such that $\nexists P=s \Rightarrow C_i$ (There doesn't exist a path from $s$ to any node in $C_i$) return None

    3.2. Else if, $C_i$ contains a negative cycle, take a maximal number of walks around without surpassing $n$ steps.

    3.3. Else, $C_i$ has no negative cycles. Delete all nodes entering $C_i$'s representative in $G^{*}$ and run BFS. Use $G_{\pi}$ to construct the walks from $s$ to all $v \in C_i$.

So my runtime problem is that it seems to that I can do better than Bellman-Ford by using BFS on the SCC graph since building $G^{*}$ is $O(|V|+|E|)$ and BFS is linear as well.

In addition, the fact that I can't make assumptions about the weight function and not knowing about negative cycles is really throwing me off here.

Thanks in advance for help and review.

$\endgroup$
3
  • $\begingroup$ Where did you encounter this exercise? Can you credit the original source? $\endgroup$
    – D.W. ♦
    Commented Aug 6 at 5:46
  • $\begingroup$ Please don't explain in the comments. Instead, revise your question so it reads well and is clear to someone who encounters it for the first time, then flag comments as 'no longer needed' once they have been addressed. $\endgroup$
    – D.W. ♦
    Commented Aug 6 at 6:15
  • $\begingroup$ How are you going to consider the following scenario: $(s, v)$-path visits multiple SCC $C_{i_j}$ with negative cycles of different vertex length? $\endgroup$
    – Smylic
    Commented Aug 9 at 14:33

0

Reset to default

Your Answer

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