Shortest path: identify edges that cause negative cycles

I have a directed graph with negative edge weights. The graph is modified by the program and sometimes will form negative cycles. When that happens, shortest path algorithms (Bellman-ford/Johnson/Floyd-Warshall) would detect the existence of such negative cycle and fail, but no other useful information is pr开发者_运维百科oduced.

I would like to identify what edge causes the negative cycle and disallow such modifications in the graph. Can someone help me with a pointer?

Thanks,

Paul

---

Paul, If you're about to add an edge (source, destination, weight), and you know the distance from destination to source, then you're creating a negative cycle if and only if new weight + old distance is negative.

On the other hand, if you've just got a graph, the bellman-ford algorithm detects negative cycles and can exhibit one when it finds one. You just need to either find an implementation that does that (rather than just failing), or write one yourself. It's not a difficult algorithm and there's lots of pseudocode on the web.

(It's probably a couple of days consultancy work if you want one custom-written for you. I do this sort of thing for a living and would be happy to.)

I'm not sure exactly what you need. I don't know, but I'd imagine that there's an on-line version of Bellman-Ford that keeps its distances up to date cheaply as new edges come in, and will scream if you add a bad one.