CODEWITHSUNDEEP
algorithmgraphminimum
Priyath Gregory
Priyath Gregory

Reputation: 987

efficient algorithm to find the minimum cost path

There is a given set of cities lets say.. A,B,C,D,E,F,G. The problem is to find the minimum cost path that covers the cities A,B,C,F. It is essential that the path covers the cities A,B,C,F. The path can, (but does not have to) go through any of the other given cities (D,E,G). Repeating a path is allowed. The path should start and end at A. How should i go about tackling a problem along similar lines?

Upvotes: 1

Views: 3072

Answers (1)

Kolmar
Kolmar

Reputation: 14224

That's a variant of Travelling Salesman Problem (TSP) in disguise.

You can see that, if you mark every city as "needed to be covered" (I'll call those "interesting" henceforth). The variant of TSP, where you are allowed to visit a node more than once, is still NP-complete.

So, knowing that the complexity of every exact solution to your problem would be exponential in the number of interesting cities, you can procede as follows:

First, precompute the shortest paths between interesting cities. This can be done with Dijkstra's algorithm run from every interesting city or Floyd-Warshall algorithm. Then either try every permutation of the order of visiting interesting cities; or use some existing TSP solver or heuristic algorithm.

So the simplest implementation goes like this:

  1. Apply Floyd-Warshall to the city graph. It's much simpler to implement than Dijkstra's. I've found a nice PDF with their comparison. It gets you the matrix with all the shortest paths for AB, AC, AF, BC, BF and CF. If you need to get the actual path as in sequence of cities, look at Path reconstruction section in Wikipedia.
  2. Try every permutation of the order of visiting interesting cities except A (i.e., only B, C and F). If you use C++, Python or Ruby, they have permutation function in the standard library. For other languages you may want to use a third-party library or search Stack Overflow for an algorithm.
  3. Find the permutation with the lowest total cost of a path. E.g., for permutation C-F-B, the total cost is AC+CF+FB+BA. You already have all those values from Floyd-Warshall, so you can simply sum them.

If you have V total cities and N interesting cities, the runtime of this implementation will be about O(V3 + N!·N)

Upvotes: 3

Related Questions