Shortest Path with k edges using Dynamic Programming

Given a weighted directed graph, we need to find the shortest path from source u to the destination v having exactly k edges. We use adjacency matrix to represent the graph in which value of adj[i][j] represents if there is an edge from vertex i to vertex j in the graph. If the value is w{w:Integer} then there is an edge from vertex i to vertex j with a weight of w else, if the value is INF then there is no edges from vertex i to vertex j in the graph. This problem is similar to finding number of path from source to destination with k edges in which we have to find total number of paths, now for this problem the shortest path will be one of the total number of paths with lowest weight cost. To understand this problem, let's take an example of directed graph with 6 vertices {0, 1, 2, 3, 4, 5}, and 9 weighted edges between them.


This is a companion discussion topic for the original entry at http://iq.opengenus.org/shortest-path-with-k-edges/