How do I find the shortest path that covers all nodes in a directed cyclic graph?

c++ algorithm graph-theory cycle shortest-path
Thaier Alkhateeb picture Thaier Alkhateeb · Apr 25, 2009 · Viewed 15.8k times · Source

I need an example of the shortest path of a directed cyclic graph from one node (it should reach to all nodes of the graph from a node that will be the input).

Please if there is an example, I need it in C++, or the algorithm.

Answer

moinudin picture moinudin · Apr 25, 2009

EDIT: Oops, misread the question. Thanks @jfclavette for picking this up. Old answer is at the end.

The problem you're trying to solve is called the Travelling salesman problem. There are many potential solutions, but it's NP-complete so you won't be able to solve for large graphs.

Old answer:

What you're trying to find is called the girth of a graph. It can be solved by setting the distances from a node to itself to infinity and using the Floyd-Warshall algorithm. The length of the shortest cycle from node i is then just the entry in position ii.

Related questions

Why do we need a priority queue in Prim's Algorithm

As my question speaks I want to know why do we use Priority queue in Prim's Algorithm? How does it saves us from using the naive way (yes I've heard of it but don't know why). I'd be very happy …

Read More
How to replace all occurrences of a character in string?

What is the effective way to replace all occurrences of a character with another character in std::string?

Read More
What is the most effective way for float and double comparison?

What would be the most efficient way to compare two double or two float values? Simply doing this is not correct: bool CompareDoubles1 (double A, double B) { return A == B; } But something like: bool CompareDoubles2 (double A, double B) { diff = …

Read More