{"id":26783,"date":"2017-12-24T15:22:53","date_gmt":"2017-12-24T09:52:53","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26783"},"modified":"2017-12-24T15:22:53","modified_gmt":"2017-12-24T09:52:53","slug":"shortest-path-exactly-k-edges-directed-weighted-graph","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/shortest-path-exactly-k-edges-directed-weighted-graph\/","title":{"rendered":"Java Programming-Shortest path with exactly k edges in a directed and weighted graph"},"content":{"rendered":"<p>Given a directed and two vertices \u2018u\u2019 and \u2018v\u2019 in it, find shortest path from \u2018u\u2019 to \u2018v\u2019 with exactly k edges on the path.<span id=\"more-130858\"><\/span><\/p>\n<p>The graph is given as <a href=\"http:\/\/www.geeksforgeeks.org\/graph-and-its-representations\/\" target=\"_blank\" rel=\"noopener noreferrer\">adjacency matrix representation<\/a> where value of graph[i][j] indicates the weight of an edge from vertex i to vertex j and a value INF(infinite) indicates no edge from i to j.<\/p>\n<p>For example consider the following graph. Let source \u2018u\u2019 be vertex 0, destination \u2018v\u2019 be 3 and k be 2. There are two walks of length 2, the walks are {0, 2, 3} and {0, 1, 3}. The shortest among the two is {0, 2, 3} and weight of path is 3+6 = 9.<\/p>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter size-full wp-image-26791\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/Shortest-path-with-exactly-k-edges-in-a-directed-and-weighted-graph.png\" alt=\"Shortest path with exactly k edges in a directed and weighted graph\" width=\"300\" height=\"203\" \/><\/p>\n<p>The idea is to browse through all paths of length k from u to v using the approach discussed in the <a href=\"http:\/\/www.geeksforgeeks.org\/count-possible-paths-source-destination-exactly-k-edges\/\" target=\"_blank\" rel=\"noopener noreferrer\">previous post<\/a> and return weight of the shortest path. A <strong>simple solution<\/strong> is to start from u, go to all adjacent vertices and recur for adjacent vertices with k as k-1, source as adjacent vertex and destination as v. Following are C++ and Java implementations of this simple solution.<\/p>\n[ad type=\u201dbanner\u201d]\n<p><strong>Java Programming<\/strong><\/p>\n[pastacode lang=\u201djava\u201d manual=\u201d%2F%2F%20Dynamic%20Programming%20based%20Java%20program%20to%20find%20shortest%20path%0A%2F%2F%20with%20exactly%20k%20edges%0Aimport%20java.util.*%3B%0Aimport%20java.lang.*%3B%0Aimport%20java.io.*%3B%0A%20%0Aclass%20ShortestPath%0A%7B%0A%20%20%20%20%2F%2F%20Define%20number%20of%20vertices%20in%20the%20graph%20and%20inifinite%20value%0A%20%20%20%20static%20final%20int%20V%20%3D%204%3B%0A%20%20%20%20static%20final%20int%20INF%20%3D%20Integer.MAX_VALUE%3B%0A%20%0A%20%20%20%20%2F%2F%20A%20naive%20recursive%20function%20to%20count%20walks%20from%20u%20to%20v%0A%20%20%20%20%2F%2F%20with%20k%20edges%0A%20%20%20%20int%20shortestPath(int%20graph%5B%5D%5B%5D%2C%20int%20u%2C%20int%20v%2C%20int%20k)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Base%20cases%0A%20%20%20%20%20%20%20%20if%20(k%20%3D%3D%200%20%26%26%20u%20%3D%3D%20v)%20%20%20%20%20%20%20%20%20%20%20%20%20return%200%3B%0A%20%20%20%20%20%20%20%20if%20(k%20%3D%3D%201%20%26%26%20graph%5Bu%5D%5Bv%5D%20!%3D%20INF)%20return%20graph%5Bu%5D%5Bv%5D%3B%0A%20%20%20%20%20%20%20%20if%20(k%20%3C%3D%200)%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20INF%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Initialize%20result%0A%20%20%20%20%20%20%20%20int%20res%20%3D%20INF%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Go%20to%20all%20adjacents%20of%20u%20and%20recur%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20V%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(graph%5Bu%5D%5Bi%5D%20!%3D%20INF%20%26%26%20u%20!%3D%20i%20%26%26%20v%20!%3D%20i)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20rec_res%20%3D%20shortestPath(graph%2C%20i%2C%20v%2C%20k-1)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(rec_res%20!%3D%20INF)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20res%20%3D%20Math.min(res%2C%20graph%5Bu%5D%5Bi%5D%20%2B%20rec_res)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20return%20res%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20public%20static%20void%20main%20(String%5B%5D%20args)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F*%20Let%20us%20create%20the%20graph%20shown%20in%20above%20diagram*%2F%0A%20%20%20%20%20%20%20%20int%20graph%5B%5D%5B%5D%20%3D%20new%20int%5B%5D%5B%5D%7B%20%7B0%2C%2010%2C%203%2C%202%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7BINF%2C%200%2C%20INF%2C%207%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7BINF%2C%20INF%2C%200%2C%206%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7BINF%2C%20INF%2C%20INF%2C%200%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%3B%0A%20%20%20%20%20%20%20%20ShortestPath%20t%20%3D%20new%20ShortestPath()%3B%0A%20%20%20%20%20%20%20%20int%20u%20%3D%200%2C%20v%20%3D%203%2C%20k%20%3D%202%3B%0A%20%20%20%20%20%20%20%20System.out.println(%22Weight%20of%20the%20shortest%20path%20is%20%22%2B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20t.shortestPath(graph%2C%20u%2C%20v%2C%20k))%3B%0A%20%20%20%20%7D%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>Output:<\/p>\n<pre>Weight of the shortest path is 9<\/pre>\n<p>The worst case time complexity of the above function is O(V<sup>k<\/sup>) where V is the number of vertices in the given graph. We can simply analyze the time complexity by drawing recursion tree. The worst occurs for a complete graph. In worst case, every internal node of recursion tree would have exactly V children.<br \/>\nWe can optimize the above solution using <strong><a href=\"http:\/\/www.geeksforgeeks.org\/dynamic-programming-set-1\/\" target=\"_blank\" rel=\"noopener noreferrer\">Dynamic Programming<\/a><\/strong>. The idea is to build a 3D table where first dimension is source, second dimension is destination, third dimension is number of edges from source to destination, and the value is count of walks. Like other <a href=\"http:\/\/www.geeksforgeeks.org\/tag\/dynamic-programming\/\" target=\"_blank\" rel=\"noopener noreferrer\">Dynamic Programming problems<\/a>, we fill the 3D table in bottom up manner.<\/p>\n[ad type=\u201dbanner\u201d]\n<p><strong>Java programming<\/strong><\/p>\n[pastacode lang=\u201djava\u201d manual=\u201d%2F%2F%20Dynamic%20Programming%20based%20Java%20program%20to%20find%20shortest%20path%20with%0A%2F%2F%20exactly%20k%20edges%0Aimport%20java.util.*%3B%0Aimport%20java.lang.*%3B%0Aimport%20java.io.*%3B%0A%20%0Aclass%20ShortestPath%0A%7B%0A%20%20%20%20%2F%2F%20Define%20number%20of%20vertices%20in%20the%20graph%20and%20inifinite%20value%0A%20%20%20%20static%20final%20int%20V%20%3D%204%3B%0A%20%20%20%20static%20final%20int%20INF%20%3D%20Integer.MAX_VALUE%3B%0A%20%0A%20%20%20%20%2F%2F%20A%20Dynamic%20programming%20based%20function%20to%20find%20the%20shortest%20path%0A%20%20%20%20%2F%2F%20from%20u%20to%20v%20with%20exactly%20k%20edges.%0A%20%20%20%20int%20shortestPath(int%20graph%5B%5D%5B%5D%2C%20int%20u%2C%20int%20v%2C%20int%20k)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Table%20to%20be%20filled%20up%20using%20DP.%20The%20value%20sp%5Bi%5D%5Bj%5D%5Be%5D%20will%0A%20%20%20%20%20%20%20%20%2F%2F%20store%20weight%20of%20the%20shortest%20path%20from%20i%20to%20j%20with%20exactly%0A%20%20%20%20%20%20%20%20%2F%2F%20k%20edges%0A%20%20%20%20%20%20%20%20int%20sp%5B%5D%5B%5D%5B%5D%20%3D%20new%20int%5BV%5D%5BV%5D%5Bk%2B1%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Loop%20for%20number%20of%20edges%20from%200%20to%20k%0A%20%20%20%20%20%20%20%20for%20(int%20e%20%3D%200%3B%20e%20%3C%3D%20k%3B%20e%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20V%3B%20i%2B%2B)%20%20%2F%2F%20for%20source%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20(int%20j%20%3D%200%3B%20j%20%3C%20V%3B%20j%2B%2B)%20%2F%2F%20for%20destination%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20initialize%20value%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20sp%5Bi%5D%5Bj%5D%5Be%5D%20%3D%20INF%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20from%20base%20cases%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(e%20%3D%3D%200%20%26%26%20i%20%3D%3D%20j)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20sp%5Bi%5D%5Bj%5D%5Be%5D%20%3D%200%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(e%20%3D%3D%201%20%26%26%20graph%5Bi%5D%5Bj%5D%20!%3D%20INF)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20sp%5Bi%5D%5Bj%5D%5Be%5D%20%3D%20graph%5Bi%5D%5Bj%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20go%20to%20adjacent%20only%20when%20number%20of%20edges%20is%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20more%20than%201%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(e%20%3E%201)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20(int%20a%20%3D%200%3B%20a%20%3C%20V%3B%20a%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20There%20should%20be%20an%20edge%20from%20i%20to%20a%20and%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20a%20should%20not%20be%20same%20as%20either%20i%20or%20j%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(graph%5Bi%5D%5Ba%5D%20!%3D%20INF%20%26%26%20i%20!%3D%20a%20%26%26%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20j!%3D%20a%20%26%26%20sp%5Ba%5D%5Bj%5D%5Be-1%5D%20!%3D%20INF)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20sp%5Bi%5D%5Bj%5D%5Be%5D%20%3D%20Math.min(sp%5Bi%5D%5Bj%5D%5Be%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20graph%5Bi%5D%5Ba%5D%20%2B%20sp%5Ba%5D%5Bj%5D%5Be-1%5D)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20return%20sp%5Bu%5D%5Bv%5D%5Bk%5D%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20public%20static%20void%20main%20(String%5B%5D%20args)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F*%20Let%20us%20create%20the%20graph%20shown%20in%20above%20diagram*%2F%0A%20%20%20%20%20%20%20%20int%20graph%5B%5D%5B%5D%20%3D%20new%20int%5B%5D%5B%5D%7B%20%7B0%2C%2010%2C%203%2C%202%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7BINF%2C%200%2C%20INF%2C%207%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7BINF%2C%20INF%2C%200%2C%206%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7BINF%2C%20INF%2C%20INF%2C%200%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%3B%0A%20%20%20%20%20%20%20%20ShortestPath%20t%20%3D%20new%20ShortestPath()%3B%0A%20%20%20%20%20%20%20%20int%20u%20%3D%200%2C%20v%20%3D%203%2C%20k%20%3D%202%3B%0A%20%20%20%20%20%20%20%20System.out.println(%22Weight%20of%20the%20shortest%20path%20is%20%22%2B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20t.shortestPath(graph%2C%20u%2C%20v%2C%20k))%3B%0A%20%20%20%20%7D%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>Output:<\/p>\n<pre>Weight of the shortest path is 9\r\n\r\n<\/pre>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>Java Programming Shortest path with exactly k edges in a directed and weighted graph The graph is given as adjacency matrix representation where value<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,70146,2139],"tags":[76591,76589,71365,83690,76588,83689,79909,79912,79910,83691,79913,79907,76592],"class_list":["post-26783","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-analysis-of-algorithm","category-java","tag-dijkstra-algorithm-in-java-with-output","tag-dijkstra-algorithm-java-adjacency-matrix","tag-dijkstra-algorithm-java-code-download","tag-dijkstras-algorithm-in-java-using-adjacency-list","tag-dijkstras-algorithm-java-using-priority-queue","tag-implementation-of-dijkstras-shortest-path-algorithm-in-java","tag-k-shortest-path-algorithm","tag-shortest-path-between-two-nodes-in-a-graph","tag-shortest-path-in-graph","tag-shortest-path-unweighted-graph-java","tag-shortest-path-with-at-most-k-edges","tag-shortest-path-with-minimum-number-of-edges","tag-single-source-shortest-path-program-in-java"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26783","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26783"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26783\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26783"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26783"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26783"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}