1

I was wondering if there is an algorithm which: given a fully connected graph of n-nodes (with different weights)... will give me the cheapest cycle to go from node A (a start node) to all other nodes, and return to node A? Is there a way to alter an algorithm like Primm's to accomplish this?

Thanks for your help

EDIT: I forgot to mention I'm dealing with a undirected graph so the in-degree = out-degree for each vertex.

Aditya
  • 5,509
  • 4
  • 31
  • 51
hershey101
  • 49
  • 1
  • 6

3 Answers3

0

Can you not modify Dijkstra, to find you the shortest path to all other nodes, and then when you have found it, the shortest path back to A?

shaw2thefloor
  • 600
  • 5
  • 20
  • 1
    According to what I understand Dijkstra finds the shortest path from the start node (A) to all other nodes... a->b, a->c,... but that would require me to return back to A after going to B to get to C. This is inefficient because I invoke the a->b edge traversal cost twice. I already have a modified version of Dijkstra to find the shortest path between all nodes but that still leaves me with many different options for cycles. I feel like this is essentially the Traveling Salesmen problem without the constrain of visiting each node only once. – hershey101 Aug 04 '11 at 16:06
0

You can try the iterative deepening A star search algorithm. It is always optimal. You need to define a heuristic though and this will depend on the problem you are trying to solve.

Jeune
  • 3,498
  • 5
  • 43
  • 54
0

There need not be any such path. It exists if and only if the in-degree of every node equals its out-degree.

What you want is the cheapest Eulerian path. The problem of finding it is called the Traveling Salesman Problem. There is not, and cannot be, a fast algorithm to solve it.

Edit: On second thought: The Traveling Salesman Problem searches for a tour that visits every node exactly once. You're asking for a tour that visits every node at least once. Thus, your problem might just be in P. I doubt it, though.

Community
  • 1
  • 1
nes1983
  • 15,209
  • 4
  • 44
  • 64
  • It seems like it would be harder than traveling salesman because with traveling salesman when you go from A to B, you don't even have to consider whether to go back to A. But I won't say it's impossible that it's easier for some other reason. – Samuel Edwin Ward Jun 26 '12 at 22:52