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

Question

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.

Thanks very much.........

Answer 1

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.

Answer 2

For non weighted graph, BFS will do the job. Since there is potential cycle in your graph, you need to keep track of visited node (you sort of need to do this for BFS anyway).

For weighted graph, bellman–Ford algorithm can be used. It is also able to detect cycles.

Answer 3

In the unweighted case: Breadth first search. In the weighted case: Dijkstra's.

Wikipedia has detailed descriptions of both.

Answer 4

In Pseudocode:

//INPUT: graph G = (V,E)
//OUTPUT: shortest cycle length
min_cycle(G)
  min = ∞
  for u in V
    len = dij_cyc(G,u)
    if min > len
      min = len
  return min    

//INPUT: graph G and vertex s
//OUTPUT: minimum distance back to s
dij_cyc(G,s)
  for u in V
    dist(u) = ∞
                   //makequeue returns a priority queue of all V
  H = makequeue(V) //using dist-values as keys with s First In
  while !H.empty?
    u = deletemin(H)
    for all edges (u,v) in E
      if dist(v) > dist(u) + l(u,v) then
        dist(v) = dist(u) + l(u,v)
        decreasekey(H,v)

  return dist(s)

This runs a slightly different Dijkstra's on each vertex. The mutated Dijkstras has a few key differences. First, all initial distances are set to ∞, even the start vertex. Second, the start vertex must be put on the queue first to make sure it comes off first since they all have the same priority. Finally, the mutated Dijkstras returns the distance back to the start node. If there was no path back to the start vertex the distance remains ∞. The minimum of all these returns from the mutated Dijkstras is the shortest path. Since Dijkstras runs at worst in O(|V|^2) and min_cycle runs this form of Dijkstras |V| times, the final running time to find the shortest cycle is O(|V|^3). If min_cyc returns ∞ then the graph is acyclic.

To return the actual path of the shortest cycle only slight modifications need to be made.