2
$\begingroup$

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,...)
  • Any general advice and comments on node-disjoint KSP are welcome.
$\endgroup$
  • $\begingroup$ Welcome to Computer Science! We don't have a strict policy for list questions, but there is a general dislike. Please note also this and this discussion; you might want to improve your question as to avoid the problems explained there. You ask forcomparison, reference (paper), explanation of added-value, insight into notation (which is quite broad on it's own) and lastly a general advice (which is not objective task). $\endgroup$ – Evil Sep 13 '16 at 1:06
  • $\begingroup$ The site works best when you ask only one question per question. Generally we suggest you ask one question, wait a little while to see if you get an answer, and then feel free to post the next question separately. (The reason for waiting is that the answer to the first question might just render the second question irrelevant.) $\endgroup$ – D.W. Sep 13 '16 at 17:39
  • $\begingroup$ We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. Please take some time to improve your post in this regard. We have collected some advice here. Thank you! $\endgroup$ – D.W. Sep 13 '16 at 17:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.