# 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) & 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\rceil ] \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?

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.

• How we can proof ? – user4249446 Feb 13 '16 at 13:15
• Maybe one of them is Dijkestra? How (1) and (3) give same things. – user4249446 Feb 13 '16 at 13:22
• all algorithms you mentioned is DP formulation? – user4249446 Feb 13 '16 at 13:33
• non of them is Dijkestra? – user4249446 Feb 13 '16 at 13:55
• Dijkstra is eficient implementation of I). But Bellman-Ford-Moore algorithm predates Dijkstra. – Shreesh Feb 13 '16 at 14:00