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

Question

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[1]$ is not bigger than $A[0]$ so we do nothing

2) $A[2]$ is bigger than $A[1]$ so $A[2]=2$

3) $A[3]$ is bigger than $A[2]$ so $A[3]=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?

Answer 1

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.