0
$\begingroup$

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:

enter image description here

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Ariel Dec 28 '17 at 15:23
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Why is the order decreasing because all the cells of the array before $t$ have $\infty$ values and afterwards they have some integer values? $\endgroup$ – Yos Dec 28 '17 at 15:24
  • 1
    $\begingroup$ 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]$. $\endgroup$ – Ariel Dec 28 '17 at 15:29
  • $\begingroup$ But how do we know that the values are monotonically decreasing? $\endgroup$ – Yos Dec 28 '17 at 15:32
  • $\begingroup$ 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. $\endgroup$ – Ariel Dec 28 '17 at 15:33
  • $\begingroup$ 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 $\endgroup$ – Yos Dec 28 '17 at 16:04

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.