Vi ger algoritmer för att hitta k kortaste vägar (inte krävs för att vara enkel) ansluta ett par hörn i en digraf. Våra algoritmer ger en implicit representation av dessa banor i en digraf med n hörn och m kanter, med tiden O(m + n log n + k). Vi kan också hitta de kortaste k-vägarna från en given källa s till varje vertex i grafen, totalt tid O(m + n log n + kn). Vi beskriver applikationer för dynamisk programmering problem inklusive Knapsack problem, sekvens anpassning, maximal inskriven polygoner, och genealogisk relation upptäckt.
Eppstein REF löste problemet med k kortaste sökvägar för riktade grafer med icke-negativa kantvikter i O(m + n log n + k) tid.
Finding the k Shortest Paths
{'venue': 'SIAM J. Comput.', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}