Question

Please answer this question prefer typing if it possible.

" Let G = (V,E) be a directed weighted graph such that all the weights are

positive. Let v and w be two vertices in G and k ≤ |V | be an integer. Design an

algorithm to find the shortest path from v to w that contains exactly k edges. Note

that the path need not be simple."

Answer 1

int shortestPath(int graph[][V], int v, int w, int k)

{

   // base cases

   if (k == 0 && v == w)             return 0;

   if (k == 1 && graph[v][w] != INF) return graph[v][w];

   if (k <= 0)                       return INF;

  

   // initialize result

   int result = INF;

  

   // Go to all adjacents of v and recur

   for (int i = 0; i < V; i++)

   {

       if (graph[v][i] != INF && v != i && w != i)

       {

           int rec_result = shortestPath(graph, i, w, k-1);

           if (rec_result != INF)

              result = min(result, graph[v][i] + rec_result);

       }

   }

   return result;

}