As part of an object tracking application, I am trying to solve a node-disjoint k-shortest path problem. My graph is (for now) k-partite. I have a single source and single sink. My edges are initially negative-positive but made non-negative by transformation.
This paper provides (in appendix) a solution but the explanation is quite evasive. They are making references to a book that I do not have: Disjoint paths in a network, J.W. Suurballe
My approach would simply consist in:
Input: Graph g for i in range(1,K+1): p[i] = dijkstra(g) g.remove_edges(p[i].edges) g.remove_nodes(p[i].nodes)
I also wonder what's the added value of doing node-splitting (fig. 3 of this) compared to my own approach.
- Could you provide some exhaustive paper on node-disjoint k-shortest path? (other than the book I mentioned since it's not available at my university).
- Can you explain the added-value of node-splitting w.r.t. my naive approach?
- Any insight into the notions of the node-disjoint KSP algorithm of the first paper would be appreciated (augmenting, interlacing, signed-path,...)
- Any general advice and comments on node-disjoint KSP are welcome.