Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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....
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.
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:
Improvements(Bellman Ford algorithm)
