CODEWITHSUNDEEP
algorithmgraph
Tarun Chabarwal
Tarun Chabarwal

Reputation: 332

Graph traversal with shortest path with any source

You're given a bidirectional weighted graph. Now you've to traverse the whole graph starting with any source making the total path length minimum. Brute force approach will be to traverse all the permutations and give the minimum.

What should be the correct approach to solve this kind of problems?

Upvotes: 0

Views: 1487

Answers (2)

Ed Rowe
Ed Rowe

Reputation: 309

This is not precisely TSP. You are effectively trying to solve for the minimum length Hamiltonian path*, without a specified start or end node. This problem is related to the TSP and like TSP, is computationally infeasible to solve in the general case. However, there are polynomial-time algorithms that can produce good approximate solutions (at worst 50% less than optimal, typically much closer). There are also algorithms which run faster but provide fewer optimality guarantees - as a crude example to prove the point, you can randomly choose a sequence of vertices in O(n) for a complete graph. What is "correct" depends on what tradeoff you want to make between optimality of the result and speed of the algorithm.

This paper: "Analysis of Christofides' heuristic: Some paths are more difficult than cycles" provides an algorithm that guarantees a result at worst 50% less than optimal. The variant that matches your case is called P* in the paper. Note that like TSP, this algorithm assumes a complete graph (all vertices connected). Given that you are allowing vertex revisitation, your graph is implicitly complete even if all vertices are not directly connected. Basically you compute the shortest path between each pair of vertices in your original graph, then create missing edges with the computed costs (and remember with them the actual paths between the vertices). You also need to replace any existing direct edges (if any) for which you've found a cheaper indirect path. This last part is necessary to ensure that the triangle inequality is satisfied, which is required to have a metric TSP which the algorithm requires. Once the result is computed, if it uses any of your synthetic edges, you've stored with them the actual paths they take so you can build the full path.

  • = With a Hamiltonian path, vertices are not revisited. The solution here will also not revisit vertices (except via the synthetic edges), because that is always more expensive than going direct to the target node, if the triangle inequality is satisfied. When we expand the Hamiltonian path to unpack the synthetic edges, then we will have revisitation and this resulting path will no longer be a Hamiltonian path.

Upvotes: 0

Vikram Bhat
Vikram Bhat

Reputation: 6246

there no polynomial time algorithm for this problem because travelling salesman is reducible to it and there is no polynomial time algorithm for TSP.But you can always improve over brute force using Dynamic Programming in this problem. You can apply DP as in TSP to reduce time complexity to O(2^N)

Held-Karp algorithm is algorithm which uses dynamic programming to get O(2^N) for TSP and can be used by slight variation on your porblem.

Otherwise use heuristic algorithm to find good solutions : -

Genetic algorithm

Ant colony optimization

Upvotes: 1

Related Questions