0
$\begingroup$

Given a digraph $𝐺 = (𝑉, 𝐸)$ with integer weights on the edges, vertex $𝑠 ∈ 𝑉$, and an array $𝑎$ of $|𝑉|$ size. Also, $𝑎[𝑣] \geqslant 𝛿 (𝑠, 𝑣)$ (shortest path between 𝑠 and 𝑣 in given graph) holds for all $𝑣 ∈ 𝑉$. The digraph is represented by adjacency lists with weights. Construct an algorithm which checks whether it is true that $𝑎 [𝑣] = 𝛿 (𝑠, 𝑣)$ for all $𝑣 ∈ 𝑉$. Algorithm running time must be linear, that is, $𝑂 (|𝑉| + |𝐸|)$.

First of all, I thought of BFS, but here we have a weighted graph. Then there was an idea to use the shortest paths algorithm for DAGs, but there is no way I can prove that given graph is acyclic. Bellman-Ford algorithm can calculate an array of shortest paths, but it performs for $𝑂 (|𝑉𝐸|)$. To be honest, I really don't know how without calculating shortest distancies solve this problem in linear time.

$\endgroup$
5
  • $\begingroup$ BFS will do, what is the problem with it being weighted? $\endgroup$
    – Phicar
    Commented Nov 10, 2020 at 18:38
  • $\begingroup$ @Phicar BFS in an instance such as this has an extra $\log |G|$ factor in the running time though. As this is a decision problem I don't think running BFS on $G$ from $s$ is the answer here. $\endgroup$
    – Mike
    Commented Nov 10, 2020 at 18:47
  • $\begingroup$ @Mike, thanks but from where are you getting this log factor? $\endgroup$
    – Phicar
    Commented Nov 10, 2020 at 18:54
  • $\begingroup$ @phicar The log factor comes when the edges have lengths taking on other values besides those in $\{1, \infty\}$. The BFS algorithm, for these general instances, maintain a queu and pick from the queu the vertex $v$ still in the queu with the smallest value of $\delta(v,s)$, which requires the queu being in sorted order. For the simpler cases where the edges all have length 1 or $\infty$ however, it suffices to calculate $N(s)$, then $N^2(S)$, and so on and so forth, and then $\delta(v,s)$ is the smallest integer $\ell$ s.t. $v \in N^{\ell}(s)$. $\endgroup$
    – Mike
    Commented Nov 10, 2020 at 19:00
  • $\begingroup$ @Mike, oh I see. Thanks! $\endgroup$
    – Phicar
    Commented Nov 10, 2020 at 19:14

1 Answer 1

Reset to default
1
$\begingroup$

HINT:

Claim: Let $a$ be an array on $V$ where $a[v] \ge \delta(V,s)$ for all $v \in V(G)$. Then $a[v] = \delta(v,s)$ iff both (a) $a[s]=0$ and (b) $a[v] \le a[w]+\ell(wv)$ for each $w \in V(G)$ and each $v$ such that $wv$ is an arc in $G$, and where $\ell(wv)$ is defined to be the length of the arc $wv$.

Can you see why this is? If not, here is another hint:

Let $v$ be any vertex in $V(G)$, and let $P$ be any path from $s$ to $v$ in $G$, including a shortest such path. Then if $a$ satisfies (a) and (b), then $a[v] \le a[s] + \ell(P)$ $=$ $\ell(P)$, where $\ell(P)$ is defined to be the length of $P$ in $G$. So then the inequality $a[v] \le \ell(P)$ must follow for each such $v$ and each such $P$. But then we are also given $a[v] \ge \delta(v,s)$ for each such $v$. So what must one conclude?

$\endgroup$
2
  • $\begingroup$ oh, I see and now have a working solution, thanks a lot! But one more question - I just have thought of negative cycles in given graph. My current algorithm wouldn't detect it, but I suppose that even if I added some kind of check for that, it definetely wouldn't work in linear time (am I right?) $\endgroup$
    – Meta
    Commented Nov 11, 2020 at 0:03
  • $\begingroup$ @Meta what I gave is fine as long as the digraph has no negative cycles, including negative-length cycles with 2 arcs. Of course you would need to check w your professor or textbook but I am about certain that this would be a given. I don't think there are any linear-time algorithms for finding whether or not a digraph has a negative-length cycle. $\endgroup$
    – Mike
    Commented Nov 11, 2020 at 18:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .