Search code examples
algorithmgraph-algorithmpseudocode

Finding minimum distance in graph for path passing minimum three nodes and finishing with start node?

I came across a problem to find optimal algorithm solving the issue: Finding minimum path in a graph from starting point to starting point(make a cycle) and visiting minimum three different nodes in the graph. For example if we have a graph G(V,E) with V={a,b,c,d,e} and edges E={(a,b,16),(a,c,300),(a,d,1),(b,c,100),(b,e,15),(c,a,10),(e,c,20)} the shortest distance will be 61 and it will visit a->c->e->b->a.

I think of using Dijkstra's algorithm for weighted graph, however I do not know how to implement the part for the constraint to visit minimum 3 nodes? It looks like the Hamiltonian cycle's problem but not using all the nodes but only part of them. Is this NP-complete problem?

Any help would be appreciated.

Solution

  • One easy way to implement this is the following:

    1. precompute all-pair shortest paths (e.g. using Floyd–Warshall or running Dijkstra for each possible start node)
    2. for each tuple (a, b, c) of distinct nodes in the graph, consider the concatenation of shortest paths from a to b, b to c and c to a.
    3. Report the minimum of all examined paths.

    The runtime will be dominated by the second step, which has runtime O(n3). So no, the problem is not NP-hard, because the number of different nodes we have to visit is fixed (in this case, 3).