Shortest Path Via Dynamic Programming Formulation? 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?

 A: 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:


*

*Initialise $d[i,j,1] = w(i,j)$, that is the length of the edge from $i$ to $j$, if there is any.

*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.
