Algorithm to find top K paths in graph, with no common vertices, negative weights?

Question

I'm using Bellman-Ford to find the shortest path through a graph with some negative weights. The graph has no possibility of loops and no bi-directional connections. I'd like to find the K shortest paths through the graph, where the paths share no nodes in common. Is there an algorithm I can look up to learn how to do this? Simple implementation is more important than speed at the moment.

Added: Thanks for comments. To be clear, I'm looking for the top K ways to get from a specified start node to a specified end node, with no other nodes in common. I need a global optimum; sequentially finding the best and deleting nodes does not give a satisfactory result. This one: https://en.wikipedia.org/wiki/Yen%27s_algorithm, gives the flavor of what I'm talking about, but in this case it requires non-negative edge costs and it also allows nodes to be shared.

Answer 1

I think that the problem can be solved finding a Minimum Cost Flow.

Let's transform the graph in the following way:

1. Replace each node v other than source and sink with two nodes v1 and v2 connected by an edge of weight 0 from v1 to v2. The incoming edges of the former v enter to v1 and the outgoing leave from v2. With this the problem is equivalent to not using those edges more than once.

2. Set capacity 1 to all the edges.

Finding a flow of value K will give you K paths that don't share a node (because of putting the capacity to 1 in those new edges). So if this flow is a minimum cost flow, you will have that those K paths also have the minimum possible sum of costs.

This is assuming that you don't have an edge connecting the source and the sink directly. Check for that corner case separately.