最短パスアルゴリズム:Bellman-fordアルゴリズム

最短パスの問題
図構造では,最短経路問題を解くには複数のアルゴリズムがあり,Bellman−Fordはそのうちの1つであり,負の重みを持つエッジを含む場合を処理することができ,同様に単一ソースの最短経路アルゴリズムであり,以前に述べたDijkstraアルゴリズムでは負の重みを持つエッジを含む場合を処理することができなかった.対応する代価は,そのアルゴリズムの時間的複雑度が高いことである.後で分析します.
ここで負重みエッジを扱うことができるのは有向図に対してであるが,無方向図では負重みエッジを含むことは負重みループを含むことを意味するため,負重みループがある場合に最短経路を求めることは無解であり,負重みループを通過するたびに距離が減少し,無制限にループしていくためである.
次に進む前に、図最短経路の1つの性質を補足する:最短経路のサブ経路も最短経路であり、数学的記述は以下の通りである:図G=(V,E)G=(V,E)G=(V,E)にp=(v 0,v 1,..,v k)p=(v_0,v_1,...,v_k)p=(v 0,v 1,...,v_k)p=(v 0,v 1,...,vk)を従点v 0 v_0 v 0から点v k v_k vkの最短経路であり、0≦i≦j≦k 0≦i≦j≦k 0≦i≦j≦kとし、p i j=(v i,v i+1,.,v j)p_{ij}=(v_i,v_{i+1},...,v_j)pij=(vi,vi+1,...,vj)は経路p p pにおける点v i v_i viから点v j v_j vjのサブパス、p i j p_pijもこの2点の間の最短パスです.証明するには、次の反証法を使用します.
パスp p p pをv 0−v i−v j−v k v_に分解すると0-v_i-v_j−vk v 0−vi−vj−vkは、w(p)=w(p 0 i)+w(p i j)+w(p j k)+w(p)=w(p_{0 i})+w(p_{ij})+w(p_{jk})w(p)=w(p 0 i)+w(pij)+w(pjk)である.v i v_からi viからv j v_j vjのより短い経路p i j’p_{ij}' pij′​, w ( p i j ′ < w ( p i j ) ) w(p_{ij}'w(pij′​Bellman-Fordアルゴリズム
Dijkstraアルゴリズムと同様に,Bellman‐Fordアルゴリズムも絶え間ない「緩和」動作によって最終解を求めた.「弛緩」は、w(u,v)w(u,v)w(u,v)w(u,v)がu u uとv v vの間の重み値を表し、d[v]d[v]d[v]d[v]がソース点s s s s sから頂点vまでの距離を表し、エッジe(u,v)e(u,v)e(u,v)e(u,v)が存在する場合、d[v]>d[u]+w(u,v)d[v]>d[u]+w(u,v)d[v]>d[u]+w(u,v)d[v(v]>d[u]+w(u,v)が存在する(すなわち、現在より優れた経路が発見される)ように、動作過程である.d[v]=d[u]+w(u,v)d[v]=d[u]+w(u,v)d[v]=d[u]+w(u,v)を更新し、経路p r e v[v]=u prev[v]=u prev[v]=uを更新する.[リラックス](Relax)のたびに最適解に近づくことがわかります.Dijkstraアルゴリズムは、現在処理されていない距離が最も小さい頂点を優先キューで選択するたびに、その頂点が処理されていないエッジを緩和する.一方,Bellman−Fordアルゴリズムはすべてのエッジを単純に緩和し,頂点の個数である∣V∣−1∣V∣−1回(∣V∣|V|∣−V∣を繰り返し実行し,時間複雑度O(∣V∣E∣)O(|V|E|)O(∣V∣E∣)O(Bellman‐Ford緩和の回数はDijkstraよりはるかに多いので,その時間的複雑さはDijkstraよりも高いことが分かった.
疑似コードは次のとおりです.

function BellmanFord(list vertices, list edges, vertex source)
    // step 1    , dist[v]        v    ，prev[v]    v     
    for each vertex v in vertices
        dist[v] = inf
        prev[v] = null

    dist[source] = 0

    // step 2     |V|-1 
    for i from 1 to size(vertices) -1 
        for each edge(u,v) with weight(u,v)  in edges
            if dist[u] + weight(u,v) < dist[v]
                dist[v] = dist[u] + weight(u,v)
                prev[v] = u
    
    // step 3          
    for each edge(u,v) with weight(u,v) in edges
        if dist[u] + weight(u,v) < dist[v]
            error "       "

    return dist[], prev[]

アルゴリズムの最適化:実際の応用では,Bellman−Fordアルゴリズムは反復緩和∣V∣−1|V|−1∣V∣−1を用いず,理論上図に存在する最大の経路長は∣V∣−1|V|−1∣V∣−1であり,実際にはこの∣V∣−1|V∣−1より小さくなることが多い,すなわち,∣V∣−1|V|−1∣V∣−1反復緩和の前から収束しており最短経路が算出されているので、あるサイクルで緩和が行われなくなった場合、現在収束していることを示し、ステップ2を終了して、次のステップで負の重み回路があるかどうかをチェックする判定をサイクル中に設定することができる.
このアルゴリズムをどう理解しますか?ある頂点がソース頂点と連通していない、すなわちエッジがないと仮定すると、この点は緩和されず、距離は更新されず、依然として無限大である.頂点とソース頂点が連通している場合、負の重み回路が存在しない場合、必ず最短経路が存在し、この最短経路p=(v 0,v 1,..,v k)p=(v_0,v_1,...,v_k)p=(v 0,v 1,...,vk)はソース点s sからv v v v v vまでの間のいずれかの最短経路(ここでv 0=s v_0=s v 0=s v 0=s,v_k=v v v)である.最大何辺ありますか?図に∣V∣|V|∣V∣個の頂点があると仮定すると、k≦∣V∣−1 k≦|V|−1 k≦∣V∣−1がある.第1ラウンドの弛緩を行う場合,弛緩されたエッジには必ずエッジ(v 0,v 1)(v_0,v_1)(v 0,v 1)が含まれ,冒頭で述べた最短パスのサブパスも最短パスの性質に違いない,v 1 v_1 v 1はその最短経路が得られており、第2ラウンドの弛緩過程において、弛緩されたエッジには必ずエッジ(v 1,v 2)エッジ(v_1,v_2)エッジ(v 1,v 2)が含まれており、今回の弛緩後、v 2 v_2 v 2もその最短経路を得た.このように、k番目のk輪緩和では、緩和された辺には必ず辺(v k−1,v k)(v_{k−1},v_k)(vk−1,vk)が含まれており、その後v k v_k vkもその最短経路を得る.すなわち,ソース頂点の最短パスと通過する辺数k k k kの頂点は,k番目のkホイールが弛緩したときに必ず確認される(最短パスが見つかった).だから、私たちは何ラウンド緩める必要がありますか.せいぜい1回でいいです.
アルゴリズムの数学的証明は「図論」または「アルゴリズム導論」の証明過程を参照することができる.
コード実装はbellmanを参照ford.cpp.最後に時間の複雑さ,最悪の場合O(∣V∣E∣)O(|V||E|)O(∣V∣E∣E∣)O,これは比較的理解しやすく,最良の場合O(∣E∣)O(|E|)O(∣E∣)O(∣E∣)O(∣E∣)O(∣E∣)O(∣E∣)O(∣E∣)O)O(|E∣E∣)O)O(|E)E∣E
アルゴリズムの応用
その1つの応用はルーティングプロトコル(距離ベクトルプロトコル)であり、これに対してrouterを参照してルーティングプロトコルテストエンジニアリングを実現した.ルーティングテーブルによるルーティングアルゴリズムを実現した.