シリーズのこれまでのパートでは、グラフ内のパスを見つけたり、他の興味深いプロパティを持つことができるDFSおよびBFSアルゴリズムを調べました。 しかし、実際には、エッジの長さが等しくないグラフ形式のタスクモデルがはるかにシンプルに見えることがよくあります。 カットの下で行う重み付きグラフで最短経路を見つける。
問題の声明
この問題では、重み付きグラフ、つまり、重みと呼ばれる特定の番号に関連付けられた各エッジを持つグラフが考慮されます。 頂点uから頂点vにつながるエッジの重みは、重み[u、v]で示されます。頂点uから頂点vへのパスを見つける必要があります。頂点のエッジの重みの合計は最小です。 この重みの合計は、頂点uから頂点vまでの距離と呼ばれ、dist [u、v]で示されます。
人生には、指定された形式で再定式化できる非常に多くのタスクがあります。たとえば、乗り換えの罰金がある場合、地下鉄での旅行時間（および最適なルート）を決定するタスクです。
簡単なものを考えましょう
エッジ（v、w）を検討してください。 端までの距離について言えますか？ 明らかに、dist [u、w]≤dist [u、v] + weight [v、w]。 証明
dist [u、v] = Kとしましょう。これは、uからvへの重みKのパスがあることを意味します。このパスにエッジ（v、w）を追加します。 重量K +重量[v、w]のuからwへのパスを取得します。 uからwまでの距離はuとvを接続するすべてのパスの長さの最小値であるため、dist [u、w]≤K + weight [v、w]
繰り返し行動しましょう。 最初は、距離は最初の頂点のみに知られています-それは0です。それぞれの瞬間に、いくつかのエッジのプロパティの充足をチェックし、違反された場合、エッジの最終頂点までの距離の既存の推定値を改善できます。 この手順は緩和と呼ばれます。
言葉は何もない、コードを見せて！
Ford＆Bellmanアルゴリズム
コードは、グラフがベクトル<vector <pair <int、int >>> edgesに格納されていることを前提としています。edges[v]は頂点vから発生するすべてのエッジのベクトルです。 エッジエッジ[v] [i]では、最初のフィールドはエッジの最後の頂点であり、2番目はその重みです。 INFは、結果の距離よりも大きいことが知られている定数です。 既知のパスがないことを示します。
void ford_bellman(int start) { // for (int i = 0; i < (int)edges.size(); ++i) { dist[i] = INF; } dist[start] = 0; // V for (int iter = 0; iter < (int)edges.size(); ++iter) { // for (int v = 0; v < (int)edges.size(); ++v) { // for (int i = 0; i < (int)edges[v].size(); ++i) { // if (dist[edges[v][i].first] > dist[v] + edges[v][i].second) { // dist[edges[v][i].first] = dist[v] + edges[v][i].second; } } } } }
アルゴリズムにはいくつのリソースが必要ですか？
グラフと応答で返される値に加えて、一定量のメモリのみを格納します。したがって、アルゴリズムに必要なメモリ量はO（1）+ <グラフと応答を格納するためのメモリ> = O（V + E）= O（E）です。各rib骨の弛緩は一定量のアクションをとります。 総rib骨-E;すべてのrib骨の弛緩はV回行われます。 したがって、アルゴリズムの時間の複雑さはO（VE）です。
私が物足りない場合はどうなりますか？
k回の反復の後、アルゴリズムはk個以下のエッジで構成されるすべての最短パスを見つけることを証明しましょう。 そして、作業の最後に、Vエッジ以下のすべての最短経路、つまり、既存のすべての最短経路を見つけることがわかります。便宜上、初期頂点uを示します。
- 基数：k = 0は明らかであり、最初のピークからそれまでのパスは正しく検出されます
- 仮定：k個以下のエッジで構成される最短パスが存在するすべての頂点vに対してk回反復した後、dist [v]は初期頂点からvまでの距離に等しい
- ステップ：k + 1のエッジで構成される最短パスがある頂点wを考えます。
- uからwへのパスの最後から2番目の頂点をvとして示します。
- vの場合、k頂点の最短パスが存在します（たとえば、wへの最短パスの始まり）。
- そのため、前の反復でvへの最短パスが見つかりました。 k + 1回目の反復でエッジ（v、w）を緩和した後、頂点wまでの距離の正しい値を取得します。
- エッジ（x、w）の各緩和は、最初の頂点から対応する長さのwまでのパスに関連付けることができるため、他のエッジの緩和中に正しい距離よりも小さい値を取得することはできません。
しかし、タイムトラベルはどうですか？
証拠では、予約が行われたことは無駄ではありませんでした-既存の最短パスがすべて検索されます。 uからvへのパスがあるが、uからvへの最短パスがない状況があります。たとえば、これらの頂点の両方が負の重みのサイクルに入る場合です。 これは、頂点間の遷移がポータルである場合、および過去と将来の両方でスローできるものと数学的に同等です。 負の重みのサイクルが存在するということは、適切な数の回転を通過した後、あなたが望む限り過去にいることができることを意味します。Ford-Bellmanアルゴリズムは、そのようなサイクルを見つける方法も提供します。サイクルがない場合、すべての最短パスはV-1エッジからの長さではなく、最後の反復では緩和されません。 最後の反復で緩和が実行されたすべてのrib骨は、最初の頂点から達成可能な負の重みのサイクルにあります。