最近、私は最短経路高速アルゴリズムについて読みました。私は、SPFA woludの標準実装が非常に遅いテストケースを構築する方法を考えています。何でも知ってますか？例えばSPFAの最悪テストケース
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
：標準の実装によって
は、私はウィキペディアからのこの1を意味します。 N個の頂点があります。最初の頂点が開始点であり、N番目の頂点が終了点です。 i番目の頂点には、（i、i + 1、1）と（1、i、2 * N）の2つのエッジがあります。ここで（a、b、c）はaからbへの重みcのエッジです。
このグラフの最短経路は1-> 2-> 3-> 4-> ...-> Nであることは容易にわかります。 spfaアルゴリズムの7行目：E（G）の各エッジ（u、v）について、より大きなidを持つ頂点が、より小さなidを持つ頂点の前にアクセスされると仮定します。 i番目の頂点はキューのmax（1、i-1）回に押し込まれます。したがって、実行時間の合計はO（N^2）です。
さらに、7行目の場合、より大きなidを持つ頂点は、より小さなidを持つ頂点より後でアクセスされ、実行時間はO（N）になります。
spfaの場合、最悪の時間の複雑さを招く7行目のトラバース順序が常に存在し、最適な時間の複雑さをもたらす7行目のトラバース順序が常に存在します。重要なことは、情報が最短経路を通ってどのように拡散されたかです。
ウィキペディアで提案されたテストケースに問題はありますか？ https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm#Worst-case_performance –
私はそれを理解していないと思います。私は10^5の頂点と5 * 10^5のエッジを持つグラフを生成しました。小さいウェイト（1と80の間のランダムウェイト）を持つフォーム（i、i + 1）の10^5エッジがあります。そして、6000から10000までの重みを持つ4 * 10^5ランダムエッジがあります。しかし、私のプログラムはこのテストケースで非常に高速に動作します。 –