Bellman Ford for directed graph G finds shortest paths within one iteration
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&lt;j_1$, then $i_2&lt;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.