1
$\begingroup$

Given directed graph G, vertex s, and all v∈V(G) are 1 edge distant from vertex s.

Is it possible to find a specific edges order (from E(G)) such that a single iteration of Bellman Ford pass over these edges in this order finds all the shortest paths (in weight) from vertex s to all vertices?

I couldn't find a counterexample for that, and it seems correct. But I have no idea how to prove it - would appreciate any hint and direction....

$\endgroup$
2
$\begingroup$

If there's no negative cycle, this is true even without the constraint that all $v\in V(G)\backslash\{s\}$ are one edge distant from vertex $s$.


Lemma. There exists a shortest path $e(v,1)e(v,2)\ldots$ (where $e(v,1),e(v,2),\ldots \in E(G)$) from $s$ to $v$ for each $v\in V(G)\backslash \{s\}$, such that for each $v_1,v_2\in V(G)\backslash \{s\}$, if there exists $i_1,i_2,j_1,j_2$ such that $e(v_1,i_1)=e(v_2,i_2)$, $e(v_1,j_1)=e(v_2,j_2)$ and $i_1<j_1$, then $i_2<j_2$.

Proof. Suppose there are such shortest paths corresponding to $v_1,\ldots,v_k$. Fix these paths and consider any shortest path $e(v_{k+1},1)e(v_{k+1},2)\ldots$ from $s$ to $v_{k+1}$. Let $i$ be the largest index such that $e(v_{k+1},i)$ appears in those fixed shortest paths corresponding to $v_1,\ldots,v_k$. Say $e(v_{k+1},i)=e(v,j)$ for some $v\in\{v_1,\ldots,v_k\}$ and some index $j$. Now consider the new path from $s$ to $v_{k+1}$: $e(v,1)\ldots e(v, j) e(v_{k+1},i+1)\ldots$ Note $e(v,1)\ldots e(v, j)$ must be a shortest path from $s$ to the vertex to which $e(v,j)$ points (otherwise $e(v,1)e(v,2)\ldots$ is not the shortest path from $s$ to $v$), the new path is no longer than $e(v_{k+1},1)e(v_{k+1},2)\ldots$ Now regarding this new path as the shortest path corresoponding to $v_{k+1}$, we have proved there are shortest paths corresponding to $v_1,\ldots,v_{k+1}$ satisfying the conditions in the lemma. Furthermore, the lemma is proved by mathematical induction. $\blacksquare$


Due to the lemma, there exists a total order of edges that is consistent with the order of edges in each shortest path selected by the lemma. Apply the first iteration of Bellman-Ford algorithm according to this total order and consider a vertex $v\in V(G)\backslash \{s\}$. Recall that $e(v,1)\ldots e(v, j)$ must be a shortest path from $s$ to the vertex to which $e(v,j)$ points, so after dealing with $e(v,1)$, the minimum distance from $s$ to the vertex to which $e(v,1)$ points is computed correctly, and after dealing with $e(v,2)$, the minimum distance from $s$ to the vertex to which $e(v,2)$ points is computed correctly, and so on. Finally we can conclude the minimum distance from $s$ to $v$ is computed correctly. As a conclusion, one iteration corresponding to this total order is sufficient.

$\endgroup$
0
$\begingroup$

what Bellman Ford algorithm does is :It relaxes every edges in graph n-1 times ,In every ith relaxation it checks if distance of a vertex from source vertex got decrease or not.

say all vertices are at infinite distance from source vertex is S (Initially).Then if you relax all edges(In any Order) single time then it will give distance to all vertices which are located at unit edge distance. see:

bellman ford worst case

Improvements(Bellman Ford algorithm)

$\endgroup$
  • $\begingroup$ edges might be negative. however, there're no negative cycles. example to possible graph: imgur.com/fBlXD0h d(S,A)=d(S,B)=d(S,C)=2, d(C,B)=d(B,A)=-1. Thus, if we pass in the order (S,A),(S,B),(S,C),(C,B),(B,A) we get correct shortest path to B and to A on the *first* Bellman Ford iteration. On other hand, for the order (C,B),(B,A),(S,A),(S,B),(S,C) we get the wrong results on the first Bellman Ford iteration, and we need another iteration! How do I prove that always exist a correct order that finds shortest paths on the first iteration? $\endgroup$ – Ami Mar 3 '18 at 22:16

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.