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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.