I have the following (directed, edge-weighted) graph problem. In a set of n vertices, G, there is a source vertex, s. I need to compute the shortest path between s and every other vertex.

I can't use Dijkstra directly since edge distances can be negative. The graph also has cycles. I realize that one can go round and round to make the total distance as low as one wants. However, I would like to find the shortest path (in terms of edge weight sums) from s to a given node, such that the path does not have any cycles.

Am I thinking about this the wrong way?


I'm not sure, but this seems to be NP-hard. Here is why.

Suppose you have an algorithm to find the simple path (i.e. path without cycles) with minimal weight between any two nodes. Using this algorithm, you can make an algorithm for finding the longest (in terms of number of edges) simple path between any two nodes simply by assigning weight $-1$ to all edges. And you can use this second algorithm to solve the Hamiltonian path problem, which is NP-complete.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.