Vi presenterar algoritmer och hårdhetsresultat för flera problem relaterade till att hitta flera enkla kortaste vägar i en graf. Vårt huvudresultat är en ny algoritm för att hitta k enkla kortaste vägar för alla par av hörn i en viktad riktad graf G = (V, E). För k = 2 vår algoritm körs i O (mn + n 2 log n) tid där m och n är antalet kanter och hörn i G. Vår strategi är baserad på att skapa lämpliga väg förlängningar för att hitta enkla kortaste vägar; denna metod skiljer sig från "detour finding" teknik som används i de flesta av de tidigare arbetena på enkla kortaste vägar, ersättningsvägar, och avstånd känslighet oracles. Vi kompletterar detta resultat genom att visa att hitta 2 enkla kortaste vägar även för ett enda par hörn är minst lika svårt som att hitta en minimum vikt cykel i G, för vilken ingen sub-mn tid algoritm är känd. Vi presenterar nya algoritmer för att generera enkla cykler och enkla vägar i G i nondecreasing ordning av sin vikt. Algoritmen för att generera enkla banor är mycket snabbare, och använder en annan variant av banor förlängningar. Vi ger också hårdhetsresultat för glesa grafer, i förhållande till komplexiteten i att beräkna en minimiviktcykel i en graf, för flera varianter av problem relaterade till att hitta k enkla banor och cykler, och vi ger relaterade resultat för oriktade grafer.
I REF presenterades nya algoritmer för att hitta k flera enkla cykler och enkla vägar i en graf, i icke-avtagande ordning på deras vikter.
Finding $k$ Simple Shortest Paths and Cycles
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}