A Shortest Path Strange Formulation, or new modeling? 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) &amp; k=1\\ \min_{1 \leq r \leq n} \left\{ d[i,r,k-1] +w(r,j) \right\}&amp; k&gt;1 \end{cases}$

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

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


  This is an exam on 2011 that solution is wrote all of them. Who Can
  Help this confusing question better understood?
Solution I) is recursive definition where $k$ is number of links. This formulation comes from same as Bellman-Ford-Moore algorithm.

Solution II) is recursive definition where $k$ is an intermediate node. $d[i,j,k]$ is length of shortest path from $i$ to $j$ involving only $1..k$ as intermediate nodes. This formulation comes from Floyd Warshall algorithm.

Solution III) is recursive definition where $k$ is again number of links. I) and III) will give same value for $d[i,j,k]$. (See Shortest Paths)

Final solution will be $d[i,j,n]$ for every case.