Shortest Path Via Dynamic Programming Formulation?

Question

We have a directed Graph $G=(V,E)$ with vertex set $V=\left\{ 1,2,...,n\right\}$. weight of each edge $(i,j)$ is shown with $w(i, j)$. if edge $(i,j)$ is not present, set $ w(i,j)= + \infty $. for each vertex $i$ put $w(i,i)=0$. we want using Dynamic Programming to find shortest path between any two vertex in this graph. by using which of them following recursive relation $d[i,j,n]$ is equal to shortest path among vertexes $i$ and $j$?

$I)$ $d[i,j,k]=\begin{cases}w(i,j) & k=1\\ min_{1 \leq r \leq n} \left\{ d[i,r,k-1] +w(r,j) \right\}& k>1 \end{cases}$

$II) d[i,j,k]=\begin{cases}w(i,j) & k=0\\ min \left\{ {d[i,j,k-1],d[i,k,k-1]+d[k,j,k-1]}\right\} & k>0 \end{cases}$

$III) d[i,j,k]=\begin{cases}w(i,j) & k=1\\ min_{1 \leq r \leq n} \left\{ {d[i,r,\lfloor k/2\rfloor ]}+d[r,j, \lceil k/2\lceil ] \right\} & k>1 \end{cases}$

this is an exam on 2011 that solution is wrote all of them. Who Can Help this confusing question better understood?

Answer 1

You want to write a program finding all the shortest paths between any two vertices in your graph. At the step $n$, the program will have saved in $d[i,j,n]$ the shortest path of length at most $n$. You do it as follows:

1. Initialise $d[i,j,1] = w(i,j)$, that is the length of the edge from $i$ to $j$, if there is any.
2. Proceed recursively: assuming you have $d[i,j,n]$, the only way to cook up a path of length $n+1$ is given by concatenating a path of length $n$ with a new edge. Therefore, you try the paths going from $i$ to vertices with an edge to $j$ and concatenate them with that edge to see if you find something shorter than $d[i,j,n]$. In fact, this is equivalent (if computationally a bit less expensive) to checking over all the vertices. It follows that the correct formula is $$d[i,j,n+1] = \min\{\min_{v\in V}d[i,v,n] + w(v,j),d[i,j,n]\}.$$ In fact, you can simply use $$d[i,j,n+1] = \min_{v\in V}d[i,v,n] + w(v,j),$$ which will give you the same result.

Here we have assumed there are no edges with negative weight. With slight modifications, this algorithm works for directed multigraphs.

Related: Dijkstra's algorithm, Bellman-Ford's algorithm, Floyd-Warshall's algorithm.