Shortest path in an undirected graph that visits k vertices

 

Consider an undirected graph. There are n vertices and m edges. All the edges have a weight associated with it.

I want to device an algorithm that will take a source vertex 's', a sink vertex 't' and a number 'k' as input. The output of the algorithm is the shortest path from s to t with k number of vertices in between s and t.

Please suggest. Thanks!

Create a distance matrix of [numvertices][numvertices] associated with your graph. Then run the Floyd algorithm but just k iteration instead of numvertices iterations as it is.

After a small research I figured out that this problem is NP-Hard. Therefore I had to use the parametrization technique to solve this problem. The algorithm that I used out is a fixed parameter tractable algorithm.

I used the Lawler's modification of the Yen's algorithm in my algorithm to solve this problem. Yen's algorithm helps to find out the first n shortest paths in a loop-less network. Here is how my algorithm goes:

  • Get the parameter k (the number of vertices in the path) from the user. Also get 'm', from the user, which is the maximum distance that the path should not exceed. This is the parameter that is going to help us solve the NP-Hard problem in polynomial time.

  • This step uses the Yen's algorithm. Find the next shortest path. Check if the path has k vertices.

    a. If yes, abort and return the path b. Else, 2

  • If the total distance of the path exceeds the parameter 'm', then abort and return 'no result'

    • The Yen's algorithm uses Dijkstra's algorithm to find the shortest path. It was fun implementing this algorithm to solve this problem.

    链接地址: http://www.djcxy.com/p/35296.html

    上一篇: 发现两个顶点之间的所有最短路径

    下一篇: 访问k个顶点的无向图中的最短路径