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.

  • 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 '19 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 '19 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 '19 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 '19 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 '19 at 16:27

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$.


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.