# How to prove that a custom iterative algorithm will determine all shortest paths to a graph node?

I'm not sure what the following algorithm does but it seems that it calculates the shortest paths from a node $t$.

Initially we're given a graph $G=(V,E)$ with non-negative weights $c(e) \ge0$ for each edge $e\in E$ and we're given a node $t\in V$.

The algorithm is as follows:

Initialize array $A$ such that $A[v] = 0$ if $v=t$ else $A[v]=\infty$.

Outer loop which is repeated continually

$\quad$ Inner loop: we scan all edges in lexicographical order and for every $e=(u,v)\in E$ we $\quad$ do the following:

$\qquad$ if $A[v] >A[u]+c(e)$ then $A[v] =A[u]+c(e)$

$\quad$ if no updates were performed in the inner loop the algorithm exits.

I need to prove by induction what the algorithm does. For example for the following graph below and if $s=b$ the initialization of $A$ will be as follows: Then the first run of the inner loop would be:

1) $A$ is not bigger than $A$ so we do nothing

2) $A$ is bigger than $A$ so $A=2$

3) $A$ is bigger than $A$ so $A=5$

The next time the inner loop will not make any updates because all the reachable nodes were already updated.

I'm not really sure if I understood correctly what the algorithm does and how to prove this inductively.

How does the fact that the algorithm checks nodes in lexicographical order come into play?

• The ordering of the edges doesn't really matter, it is only there to specify some order relative to which you will iterate them. The algorithm remains correct for every ordering. – Ariel Dec 28 '17 at 15:23

You can prove by induction that for every iteration $i$, the array $A$ during this iteration, $A_i$, contains the weights of some paths originating at $t$. More formally, for all $v\in V$, $A_i[v]$ is either $\infty$ or the weight of some path from $t$ to $v$.
Now, it is easy to show that the values of $A_i$ are monotonically non increasing, which combined with the above statement implies that the algorithm terminates. I leave the details to you.
• Why is the order decreasing because all the cells of the array before $t$ have $\infty$ values and afterwards they have some integer values? – Yos Dec 28 '17 at 15:24
• No, according to what you're saying the integer values may yet grow. Monotonicity here means that for $i<j$ and every $v\in V$ : $A_i[v] \ge A_j[v]$. – Ariel Dec 28 '17 at 15:29
• Examine your algorithm carefully, when and how is $A$ being updated? I think you have enough details to write the complete proof on your own. – Ariel Dec 28 '17 at 15:33
• In my example the array $A$ finally is: $\infty,0,0+2,2+3=\infty,0,2,5$ according to the explanation I gave in the OP. If it's correct then the values are increasing – Yos Dec 28 '17 at 16:04