3
$\begingroup$

Given a directed graph $G = (V, E)$, with all edge weights being non-negative, someone has written a program that he/she claims implements Dijkstra's algorithm.
For a fixed starting vertex $s$, the program produces $v.d$ (shortest distance from $s$) and $v.\pi$ (immediate predecessor in the shortest path) for each vertex $v \in V$.

Question: How to check whether the $d$ and $\pi$ values match those of some shortest-paths tree of $G$ in linear time (i.e., $O(V + E)$)?


My attempts:

  1. Feed the $d$ and $\pi$ values into a running instance of our real Dijkstra algorithm and check if some step would go wrong.
    The key point here is how to reduce the running time of the real Dijkstra algorithm from $O(E \log V)$ to $O(V + E)$, taking advantage of the existing $v.d$ and $v.\pi$ values.

  2. To check the triangle inequality condition: For all edges $(u,v) \in E$, we have $d(s,v) \le d(s,u) + w(u,v)$.

    Question: However, is the triangle inequality condition a sufficient one for some directed, rooted spanning tree to be a shortest-paths tree?

$\endgroup$
  • $\begingroup$ As per the discussion after my answer below, we should remove the path part $v.\pi$ and check only if $v.d$ is correct. That will be a much better question. $\endgroup$ – InformedA Oct 18 '14 at 16:26
  • $\begingroup$ @randomA I am not sure about this idea. Maybe you can explain it more clearly in your answer. Thanks. $\endgroup$ – hengxin Oct 19 '14 at 4:30
  • $\begingroup$ It is not actually an idea about solving the new problem that you just clarified to me though. I misread your question so I answered another understanding of your question. $\endgroup$ – InformedA Oct 19 '14 at 6:02
  • 1
    $\begingroup$ This is a standard exercise. We're not here to do your exercises for you. I think you should put in more effort on your own. Hint: I recommend you try some examples. Try some example graphs, run Dijkstra's (a correct version), look at the $d$ and $\pi$ values, and look for patterns. If $(u,v) \in E$, what can you say about the relationship between $d(s,v)$ and $d(s,u) + w(u,v)$? Do you notice any patterns in your examples? Now try to prove those patterns always hold. I think you'll find that if you give this a try, you should soon be able to make some progress on this problem. $\endgroup$ – D.W. Oct 20 '14 at 0:49
1
$\begingroup$

Hint:

  1. This question is telling us to find an algorithm in $O(V+E)$ which immediately suggests us some kind of search in the graph, i.e, DFS.
  2. Using $\pi$ we should be able to build a candidate tree $T$ rooted in $s$ to test if it's shortest-path tree.
  3. In each shortest-path tree, we have that for every $v \in V(T)$, $v \neq s$, the equality $d(\pi(v)) + w(\pi(v), v) = d(v)$ holds.
$\endgroup$
0
$\begingroup$

We can prove this in a similar way to how you prove Bellman-Ford has converged. Let $d(v)$ be the distance from root to $v$ in this rooted spanning tree and let $\delta(v)$ be the shortest distance from $s$ to $v$ in the graph. If $d(v) = \delta(v)$, then attempting to relax all edges in $E$ should not change anything. When I say "relax" I mean, invoke the triangle inequality:

relax(u, v):
  if d(v) > d(u) + w(u,v):
    d(v) = d(u) + w(u,v)
    pi(v) = u

If, at any point, a relaxation changes $d(v)$, then clearly the spanning tree path is not the shortest. This makes sense intuitively, but we can prove it formally.

Claim: If $d(v) > \delta(v)$ for some node $v$, then some node $v'$ on the true shortest path from $s$ to $v$ has value $d(v')$ such that $d(v') > d(u) + w(u,v')$ for some edge $(u,v') \in E$.

Proof: By induction on the number of nodes $n$ in the shortest path from $s$ to $v$.

Base Case: When we have $n = 2$, then we have one edge in the shortest path $s \rightarrow v$. Thus, the true shortest path has distance $w(s,v)$. If $d(v) > \delta(v)$ then:

$$\begin{align*} d(v) &> \delta(v)\\ & = w(s,v)\\ & = d(s) + w(s,v) \end{align*}$$

Inductive Case: Assume the claim holds for the first $n-1$ nodes on the shortest path $\{s, u_1, u_2, \ldots, u_{n-2}, v\}$. We now prove it holds for the addition of $v$ to the shortest path.

If the claim holds for this whole path, then either some node prior to $v$ in the path triggers the if condition, and the claim holds by induction. Otherwise, we have for all nodes $u$ prior to $v$ that $d(u) = \delta(u)$ and $d(v) > \delta(v)$. Now we need only prove that $d(v) > d(u_{n-2}) + w(u_{n-2}, v)$:

$$\begin{align*} d(v) &> \delta(v)\\ & = \delta(u_{n-2}) + w(u_{n-2}, v) & \text{by construction of the shortest path}\\ & = d(u_{n-2}) + w(u_{n-2}, v) \quad \square \end{align*}$$

Thus, after running the relaxation step on all edges, you should have your answer.

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