# node-disjoint k-shortest path

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.

Questions:

• 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,...)