Worst Testfall für SPFA

Question

Kürzlich habe ich über Shortest Path Faster Algorithmus gelesen. Ich frage mich, wie man einen Testfall erstellt, für den die Standard-Implementierung von SPFA wolud sehr, sehr langsam ist. Kennst du irgendwelche?

von Standard-Implementierung, meine ich diesen von Wikipedia:

procedure Shortest-Path-Faster-Algorithm(G, s) 
1 for each vertex v ≠ s in V(G) 
2  d(v) := ∞ 
3 d(s) := 0 
4 offer s into Q 
5 while Q is not empty 
6  u := poll Q 
7  for each edge (u, v) in E(G) 
8   if d(u) + w(u, v) < d(v) then 
9    d(v) := d(u) + w(u, v) 
10    if v is not in Q then 
11     offer v into Q 

Answer 1

Zum Beispiel. Es gibt N Ecken. Der erste Eckpunkt ist der Anfang und der n-te Eckpunkt ist das Ende. Für den i-ten Knoten gibt es 2 Kanten: (i, i + 1, 1) und (1, i, 2 * N) wobei (a, b, c) bedeutet, dass es eine Kante von a nach b mit dem Gewicht c gibt.

Es ist leicht zu sehen, dass der kürzeste Pfad in diesem Graphen 1-> 2-> 3-> 4 -> ...-> N ist. Nehmen Sie an, dass für die 7. Zeile Ihres spfa-Algorithmus: für jede Kante (u, v) in E (G) der Scheitelpunkt mit der größeren ID vor dem Scheitelpunkt mit der kleineren ID zugegriffen wird. Dann wird der i-te Scheitelpunkt maximal (1, i-1) in die Warteschlange geschoben. Die gesamte Ausführungszeit ist also O (N^2).

Weiter, wenn für die 7. Zeile der Scheitelpunkt mit der größeren ID später als der Scheitelpunkt mit der kleineren ID abgerufen wird, dann ist die Ausführungszeit O (N).

Für spfa gibt es immer eine Polygonzug-Reihenfolge der 7. Zeile, die zur Komplexität der schlechtesten Zeit führt, und es existiert immer eine Polygonzug-Reihenfolge der 7. Zeile, was zur besten Zeitkomplexität führt. Entscheidend ist, wie die Informationen auf dem kürzesten Weg verbreitet werden.