[Solved]: Algorithm to find shortest path between two nodes

Problem Detail: 

I want an algorithm similar to Dijkstra or Bellman-Ford for finding the shortest path between two nodes in a directed graph, but with an additional constraint.

The additional constraint is that there are $N$ sets of special edges with weight $0$ such that a path is not considered valid if it traverses one edge in a set but not the remaining edges in that set.

Note that these $N$ sets of edges are disjoint such that no edge belongs to more than one of the $N$ sets. The number of edges in each set is around 3 to 6. And there are a large number of these sets. About $50\%$ of edges belong to a set, the rest don't belong to a set and can be traversed normally.

Does such an algorithm exist? Can such an algorithm exist that is better than brute force?

Asked By : dan

Answered By : Tom van der Zanden

It is $NP$-complete, and thus it is unlikely that a polynomial algorithm ("better than brute force") exists. Proof is by reduction from Hamiltonian $s-t$-Path:

Every edge in the input graph $G=(V,E)$ is given weight $1$. The graph is then duplicated, and special (weight 0) edges are added between corresponding vertices in the two graphs. We thus get two copies of the original graph, and the copies are linked by $|V|$ special edges between the two copies of the same vertex. Call these new edges the 'copy' edges.

$|V|$ vertices are added to the graph and connect in a chain with $|V|-1$ new special (weight) 0 edges. Another special (weight 0) edge is added to connect the end vertex to $s$. Call these new edges the 'chain' edges.

Partition the $2|V|$ new edges into $|V|$ edge sets that each consist of one copy edge and one chain edge.

We now try to find a shortest path between the start of the chain and vertex $t$ that satisfies your requirement of traversing either all or none of the edges from each edge set. Such a path must start by traversing the full chain, so it must contain all chain edges, so it must contain all copy edges, so it must visit every vertex of the original graph; therefore, omitting all special edges from it will produce a Hamiltonian path from $s$ to $t$, if one exists.

Deciding whether a Hamiltonian path between arbitrary edges $s$ and $t$ exists is known to be $NP$-complete, so your problem is $NP$-hard: if you can find a polynomial algorithm for it (such as Dijkstra's), you will have proved $P=NP$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37387