Können wir k kürzeste Wege zwischen allen Paaren schneller finden, als das paarweise Problem wiederholt zu lösen?

9

Ich möchte kürzesten Weg ( k wäre kleiner als 10) zwischen allen Paaren in einem Graphen erzeugen . Die Grafik ist (eigentlich eine U-Bahn-Karte):kk

  • positiv gewichtet
  • ungerichtet
  • spärlich
  • mit etwa 100 Knoten

Mein aktueller Plan ist es, kürzestes Routingk auf jedes Paar anzuwenden ; Ich suche jetzt nach einer effizienteren Alternative (möglicherweise mit dynamischer Programmierung).

algorithms graphs optimization shortest-path Franklin Yu
quelle
3
Ehrlich gesagt, ist es für 100 Eckpunkte unwahrscheinlich, dass Sie etwas Effizienteres benötigen, als jedes der 45.000 paarweisen Probleme zu lösen.
David Richerby

Antworten:

6

k

k

Dies scheint ein recht junges Forschungsgebiet zu sein. Ein kürzlich veröffentlichtes Papier von Agarwal und Ramachandran ist auf dem ArXiv zu finden [1]. Der Abschnitt mit den vorherigen Arbeiten gibt Ihnen auch einen Einblick in die Geschichte des Problems.

Das aller Paarek

Hier ist es in der Tat die beste Wahl, den Eppsteins-Algorithmus nur wiederholt anzuwenden [2]. Die allgemeine Beobachtung, dass eine wiederholte Anwendung eines Algorithmus für die Single-Source-Version des Problems der schnellste Ansatz ist, wurde bereits 1977 von EL Lawler gemacht [3]; Eppstein bietet den bislang schnellsten Algorithmus für dieses Teilproblem.

Verweise

k

[2] Eppstein, D. Die k kürzesten Wege finden. SIAM Journal on Computing 28, 2 (1999), 652–673.

[3] Lawler, EL Kommentar zu einer Berechnung der k kürzesten Pfade in einem Diagramm. Mitteilungen der ACM, 20 (8): 603–605, 1977.

Flunkern
quelle
Danke. Da ich mit U-Bahn-Karten arbeite, muss sie ein einfacher Pfad sein (es macht keinen Sinn, wenn meine Software die Leute zum Hin- und Herbewegen führt), also würde ich wohl einfach mit Yans Algorithmus arbeiten .
Franklin Yu
Interessant und ziemlich überraschend, dass anscheinend 10.000 Fälle eines Problems nicht schneller gelöst werden können als nur 10.000 Einzelfälle nacheinander zu lösen.
Gnasher729
die Idee von Pfaden mit in den „kürzesten Wege“ enthalten Schleifen scheint nicht eingängig und ungewöhnlich , weil es scheinbar ein Äquivalent „Pfad“ ist mit der Schleife entfernt, und man fragt sich auch , wenn diese effizient von den einfachen Pfaden usw. aufgebaut werden kann ...
vzn