A note on k-shortest paths problem

✍ Scribed by Nick Gravin; Ning Chen

• Publisher: John Wiley and Sons
• Year: 2010
• Tongue: English
• Weight: 66 KB
• Volume: 67
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20510

✦ Synopsis

It is well-known that in a directed graph, if deleting any edge will not affect the shortest distance between two specific vertices s and t, then there are two edge-disjoint paths from s to t and both of them are shortest paths. In this article, we generalize this to shortest k edgedisjoint s-t paths for any positive integer k.