Shortest path in an undirected graph that visits k vertices

2
votes

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!

2
graphshortest-path
You mention that edges have a weight. Did you mean to ask "Find the path from s to t of length k+2 with the minimal sum of the edge weights?" – mbeckish
is this what you are looking for? stackoverflow.com/questions/9996808/… – Ignacio
@mbeckish That is absolutely correct. To be more precise, I need to find a path from s to t with k vertices in between s and t. Additionally, the path must have a minimal sum when compared to other similar paths that have k vertices in between s and t. – eddyrokr

2 Answers

1
votes

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.

1
votes

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:

  1. 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.

  2. 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

  3. 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.