# Given directed connected weighted graph, check if d(v) = delta(s,v)

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.

• 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)$? – j_random_hacker Mar 29 '19 at 14:52
• Sorry, I still can't figure it out. assuming 𝑑(𝑣)=𝑑𝑒𝑙𝑡𝑎(𝑠,𝑣) for all v, it means 𝑑(𝑢) is greater than each "incoming" vertex 𝑑(𝑢). is that you intent? – Keren Mar 29 '19 at 15:27
• 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 ____. – j_random_hacker Mar 29 '19 at 15:57
• (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.) – j_random_hacker Mar 29 '19 at 15:58
• 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 :( – Keren Mar 29 '19 at 16:27

## 1 Answer

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