[Math] Relax function on Bellman Ford Algorithms

algorithmscomputer sciencegraph theoryrecursive algorithmstrees

In a Weighted Directed Graph $G$ (with positive weights), with $n$ vertex and $m$ edges, we want to calculate the shortest path from vertex $1$ to other vertexes. we use $1$-dimensional array $D = (d_1,\cdots,d_n)$, and $D_1=0$ and others filled with $+\infty$. for updating the array we just premit to use the $\mathrm{Relax}(u, v)$ function,

  1. if $(\, D[v] > D[u] + W(u, v) \,)$ then
  2. $\quad D(v) \leftarrow D(u)+W(u,v)$
  3. endif

In which $W(u, v)$ is the weight of $u \implies v$ edge. How many time (at least) we must call the Relax function to ensure that for each vertex $u$, $D[u]$ be equals to length of shortest path from vertex $1$ to $u$.

Solution:

My TA says this is just Bellman-Ford and $m \times n$ times we must call, but maybe i think we can use Dijkstra and need $m$ times.

Anyone could help me?

Best Answer

If the only thing you are allowed to do is use the Relax function, then indeed you're basically running Bellman-Ford. Your intuition about using Dijkstra is right in the sense that, since all weights are positive, you could apply that algorithm, but then you need to keep track of the vertex that has the current shortest distance from vertex 1. If you're not allowed to do that, then your TA is right.

So there are two solutions, in the first one you call relax $m \times n$ times:

for _ in 1 .. n: for i in 1 ... n: for every edge (i, j): Relax(i, j)

This code is basically Bellman-Ford, without a posterior check for a negative cycle. This check can be omitted since all weights are positive.

Another solution calls relax $m$ times, but searches for the vertex with the shortest distance at each step:

function MinDistance( S, D ): min = None for i in S: if min is None or D[i] < min: min = D[i] argmin = i return argmin

function InefficientDijkstra(): S = set() D[1] = 0 S.add(1) while not S.empty(): argmin = MinDistance( S, D ) for every edge (argmin, j): old_dist = D[j] Relax(argmin, j) if D[j] < old_dist: S.add(j) S.remove(argmin)

This is a very inefficient way to implement Dijkstra, but it calls the Relax function only $m$ times.

Related Question