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?