algorithm - Graph traversal with shortest path with any source

Question

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?

Answer 1

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