2
$\begingroup$

I'm having some hard time with this problem. Can someone give me some clue/guidance?

This is an homework question, so please don't just solve it.

Given a weighted directed connected graph $G = (V,E)$ and given another function $d: V \to \mathbb{R}^+$ (including zero), find a linear time algorithm that checks if $d(v)=\text{delta}(s,v)$ for each $v$, for some fixed vertex $s$.

$\text{delta}(s,v)$ is like in Dijkstra algorithm, meaning shortest path from $s$ to $v$.

My thought is to make use of BST to check if these functions are equal, but I can't avoid running Dijkstra for it.

$\endgroup$
  • 2
    $\begingroup$ Given a vertex $v$ and all its neighbours $u_1, \dots, u_k$, and assuming that in fact $d(v) = delta(s, v)$, what can you say about $d(v)$ and (some of) the values $d(u_1), \dots, d(u_k)$? $\endgroup$ – j_random_hacker Mar 29 at 14:52
  • $\begingroup$ Sorry, I still can't figure it out. assuming 𝑑(𝑣)=𝑑𝑒𝑙𝑡𝑎(𝑠,𝑣) for all v, it means 𝑑(𝑢) is greater than each "incoming" vertex 𝑑(𝑢). is that you intent? $\endgroup$ – Keren Mar 29 at 15:27
  • $\begingroup$ We don't know (or at least don't assume that we know) which vertices are incoming. But we still know that for at least one neighbour $u_i$ of $v$, either ____ or ____. $\endgroup$ – j_random_hacker Mar 29 at 15:57
  • $\begingroup$ (I'm not yet sure that this is "the right" way to go about this, but it seems likely that the property I have in mind will turn out to be useful.) $\endgroup$ – j_random_hacker Mar 29 at 15:58
  • $\begingroup$ Thanks for your help, appreciated a lot!. But still - is it a property of greater/less than? either d(u) > delta(s,u(i)) or equals? and then sort them somehow? I'm stuck with the idea of running Dijkstra :( $\endgroup$ – Keren Mar 29 at 16:27
1
$\begingroup$

If $d$ indeed represents the length of the shortest path, we must have

$$ d(v)= \begin{cases} 0, &\text{if $v=s$,}\\ \displaystyle\min_{u:(u,v)\in E}\{d(u)+w(u,v)\}, &\text{otherwise,} \end{cases} $$

where $w(u,v)$ is the weight of the edge $(u,v)$.

So you can check whether $d$ satisfies this property for all $v$. It takes only linear time. If $d$ does not satisfy this property, it cannot represent the length of the shortest path. However, if $d$ does satisfy this property, does it really represent the length of the shortest path? I'll let you figure out this part.

For a further hint:

Note what you need to prove is that, for all $v$, $d(v)$ is length of the shortest path from $s$ to $v$. Suppose the shortest path from $s$ to $v$ contains $k$ edges, you may try a mathematical induction on $k$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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