さまざまな都市が道路で接続され、各道路が一定の距離を持つ地図があると想像してください。の ベルマン・フォードアルゴリズム は、一部の道路の長さが負の場合でも、ある都市から他のすべての都市への最短経路を見つけるのに役立つガイドのようなものです。それはまるで GPS コンピュータの場合、ネットワーク内のある地点から別の地点に移動する最も速い方法を見つけるのに役立ちます。この記事では、このアルゴリズムがどのように機能するのか、そしてなぜこのアルゴリズムが日常の問題を解決するのに非常に便利なのかを詳しく見ていきます。
目次
- ベルマン・フォードアルゴリズム
- Bellman Ford アルゴリズムの背後にある考え方
- Bellman-Ford のエッジ緩和の原理
- エッジを N-1 回緩和すると、単一ソースの最短パスが得られるのはなぜですか?
- N 回目の緩和における距離の減少が負のサイクルの存在を示すのはなぜですか?
- グラフ内の負のサイクルを検出するための Bellman-Ford アルゴリズムの動作
- Bellman-Ford を使用して有向重み付きグラフで負のサイクルを見つけるアルゴリズム
- アルゴリズムでの切断されたグラフの処理
- Bellman-Ford アルゴリズムの複雑さの分析
- Bellman Ford のアルゴリズム アプリケーション
- Bellman Ford のアルゴリズムの欠点
ベルマン・フォードアルゴリズム
ベルマン・フォード です 単一ソース グラフ内の特定のソース頂点と他のすべての頂点の間の最短パスを決定する最短パス アルゴリズム。このアルゴリズムは両方で使用できます 重み付けされた そして 重み付けされていない グラフ。
メガバイトとギガバイトの違いは何ですか
あ ベルマン・フォード アルゴリズムも、次と同様に、グラフ内の最短パスを見つけることが保証されています。 ダイクストラのアルゴリズム 。ベルマンフォードはそれよりも遅いですが、 ダイクストラのアルゴリズム 、次のグラフを処理できます。 負のエッジの重み 、より多用途になります。存在する場合、最短パスは見つかりません。 負のサイクル グラフで。負のサイクルを無限回繰り返し続けると、(パスの長さは増加しても) パスのコストは減少し続けます。結果として、 ベルマン・フォード を検出することもできます 負のサイクル 、これは重要な機能です。
Bellman Ford アルゴリズムの背後にある考え方:
Bellman-Ford アルゴリズムの主な原理は、単一のソースから開始して各ノードまでの距離を計算することです。距離は最初は不明で無限であると想定されますが、時間の経過とともに、アルゴリズムはいくつかのより短いパスを特定することでそれらのパスを緩和します。したがって、ベルマンフォードは以下に基づいていると言われています。 リラクゼーションの原理 。
Bellman-Ford のエッジ緩和の原則:
- それは、次のグラフに対して次のように述べています。 N 頂点、すべてのエッジはリラックスする必要があります N-1 単一ソースの最短パスを計算するのに 3 回かかります。
- 負のサイクルが存在するかどうかを検出するには、もう一度すべてのエッジを緩和し、いずれかのノードの最短距離が減少した場合、負のサイクルが存在すると言えます。要するにエッジを緩めると N 回であり、ノード間の任意のノードの最短距離に変化がある場合 N-1st そして N番目 負のサイクルよりも緩和が存在し、それ以外の場合は存在しません。
エッジを N-1 回緩和すると、単一ソースの最短パスが得られるのはなぜですか?
最悪のシナリオでは、2 つの頂点間の最短パスは最大でも N-1 エッジ、どこ N 頂点の数です。これは、グラフ内の単純なパスが次のとおりであるためです。 N 頂点には最大でも次の値を含めることができます N-1 頂点を再訪せずに閉ループを形成することは不可能であるため、エッジ。
エッジを緩めることで N-1 ベルマン・フォード アルゴリズムは、ソース頂点から到達可能な負の重みサイクルがグラフに含まれていないことを前提として、すべての頂点の距離推定値が最適な値に更新されていることを確認します。グラフにソース頂点から到達可能な負の重みサイクルが含まれている場合、アルゴリズムはそれを検出できます。 N-1 負のサイクルにより最短経路長が中断されるため、繰り返しが行われます。
文字列.値
要約すると、エッジを緩和する N-1 Bellman-Ford アルゴリズムで 8 回実行すると、アルゴリズムが次までの長さのすべての可能なパスを探索したことが保証されます。 N-1 、これはグラフ内の最短経路の可能な最大長です。 N 頂点。これにより、負の重みサイクルがない場合、アルゴリズムはソース頂点から他のすべての頂点への最短パスを正しく計算できます。
N 回目の緩和における距離の減少が負のサイクルの存在を示すのはなぜですか?
前述したように、他のすべてのノードへの単一ソースの最短パスを実現するには、 N-1 リラクゼーション。 N 番目の緩和により任意のノードの最短距離がさらに短縮される場合、負の重みを持つ特定のエッジがもう一度横断されたことを意味します。作業中に次のことに注意することが重要です。 N-1 緩和では、各頂点は 1 回だけ通過すると仮定しました。ただし、N 回目の緩和中の距離の減少は、頂点を再訪していることを示しています。
グラフ内の負のサイクルを検出するための Bellman-Ford アルゴリズムの動作:
以下に示すグラフがあり、ベルマン・フォードを使用して負のサイクルが存在するかどうかを調べたいとします。
初期グラフ
ステップ1： 距離配列 Dist[] を初期化して、ソース頂点から各頂点の最短距離を保存します。最初はソースの距離は 0 で、他の頂点の距離は無限大になります。
距離配列を初期化する
ステップ2： 1 回目のリラックス中に、エッジのリラックスを開始します。
abcと数字
- B の現在の距離> (A の距離) + (A から B までの重み) つまり、無限大> 0 + 5
- したがって、Dist[B] = 5
1回目のリラクゼーション
ステップ 3: 2回目のリラックス中:
- D の現在の距離> (B の距離) + (B から D までの重み) つまり、無限大> 5 + 2
- 距離[D] = 7
- C の現在の距離> (B の距離) + (B から C までの重み) つまり、無限大> 5 + 1
- 距離[C] = 6
2回目のリラックス
ステップ 4: 3回目のリラックス中:
- F の現在の距離> (D の距離) + (D から F までの重み) つまり、無限大> 7 + 2
- 距離[F] = 9
- E の現在の距離> (C の距離) + (C から E までの重み) つまり、無限大> 6 + 1
- 距離[E] = 7
3回目のリラックス
ステップ5: 4回目のリラックス中:
- D の現在の距離> (E の距離) + (E から D までの重み) つまり、7> 7 + (-1)
- 距離[D] = 6
- E の現在の距離> (F の距離) + (F から E までの重み) つまり、7> 9 + (-3)
- 距離[E] = 6
4回目のリラックス
ステップ6: 5回目のリラクゼーション中:
- F の現在の距離> (D の距離) + (D から F までの重み) つまり、9> 6 + 2
- 距離[F] = 8
- D の現在の距離> (E の距離) + (E から D までの重み) つまり、6> 6 + (-1)
- 距離[D] = 5
- グラフには 6 つの頂点があるため、5 回目の緩和中にすべての頂点の最短距離が計算されるはずです。
5回目のリラックス
ステップ 7: ここで、最後の緩和、つまり 6 回目の緩和は、5 回目の緩和の距離配列に変化がある場合、負のサイクルの存在を示すはずです。
6 回目の緩和では、次のような変化が見られます。
- E の現在の距離> (F の距離) + (F から E までの重み) つまり、6> 8 + (-3)
- 距離[E]=5
- F の現在の距離> (D の距離) + (D から F までの重み) つまり、8> 5 + 2
- 距離[F]=7
距離配列の変化を観察するので、グラフ内に負のサイクルが存在すると結論付けることができます。
6回目のリラクゼーション
部分文字列 java結果： グラフには負のサイクル (D->F->E) が存在します。
Bellman-Ford を使用して有向重み付きグラフで負のサイクルを見つけるアルゴリズム:
- 各頂点の距離配列 dist[] を初期化します。 で ' として dist[v] = 無限大 。
- 任意の頂点 (「0」としましょう) をソースとして想定し、割り当てます 距離 = 0 。
- 全部リラックスして エッジ(u,v,weight) N-1 以下の条件に従って回数:
- dist[v] = 最小(dist[v], distance[u] + 重み)
- ここで、もう一度すべてのエッジをリラックスさせます。 N番目 以下の 2 つのケースに基づいて、負のサイクルを検出できます。
- ケース 1 (負のサイクルが存在する): edge(u, v,weight)、dist[u] + ウェイトの場合
- ケース 2 (負のサイクルなし) : ケース 1 はすべてのエッジで失敗します。
- ケース 1 (負のサイクルが存在する): edge(u, v,weight)、dist[u] + ウェイトの場合
アルゴリズムでの切断されたグラフの処理:
特定のグラフが切断されている場合、上記のアルゴリズムとプログラムは機能しない可能性があります。すべての頂点がソース頂点から到達可能な場合に機能します 0 。
切断されたグラフを処理するには、次の頂点に対して上記のアルゴリズムを繰り返すことができます。 距離 = 無限大、 または単に訪問されていない頂点に対してです。
上記のアプローチの実装を以下に示します。
C++ // A C++ program for Bellman-Ford's single source // shortest path algorithm. #include using namespace std; // a structure to represent a weighted edge in graph struct Edge { int src, dest, weight; }; // a structure to represent a connected, directed and // weighted graph struct Graph { // V->頂点の数、E-> エッジの数 int V、E; // グラフはエッジの配列として表現されます。 struct Edge* エッジ; }; // V 頂点と E エッジを持つグラフを作成します struct Graph* createGraph(int V, int E) { struct Graph* chart = new Graph; グラフ -> V = V; グラフ->E = E; グラフ->エッジ = 新しいエッジ[E]; グラフを返します。 } // 解を出力するために使用されるユーティリティ関数 void printArr(int dist[], int n) { printf('ソースからの頂点距離
'); for (int i = 0; i< n; ++i) printf('%d %d
', i, dist[i]); } // The main function that finds shortest distances from src // to all other vertices using Bellman-Ford algorithm. The // function also detects negative weight cycle void BellmanFord(struct Graph* graph, int src) { int V = graph->V; int E = グラフ->E; int dist[V]; // ステップ 1: src から他のすべての頂点までの距離を // INFINITE として初期化します (int i = 0; i< V; i++) dist[i] = INT_MAX; dist[src] = 0; // Step 2: Relax all edges |V| - 1 times. A simple // shortest path from src to any other vertex can have // at-most |V| - 1 edges for (int i = 1; i <= V - 1; i++) { for (int j = 0; j < E; j++) { int u = graph->エッジ[j].src; int v = グラフ->エッジ[j].dest; int 重み = グラフ->エッジ[j].weight; if (dist[u] != INT_MAX && dist[u] + 重み< dist[v]) dist[v] = dist[u] + weight; } } // Step 3: check for negative-weight cycles. The above // step guarantees shortest distances if graph doesn't // contain negative weight cycle. If we get a shorter // path, then there is a cycle. for (int i = 0; i < E; i++) { int u = graph->エッジ[i].src; int v = グラフ->エッジ[i].dest; int 重み = グラフ->エッジ[i].weight; if (dist[u] != INT_MAX && dist[u] + 重み< dist[v]) { printf('Graph contains negative weight cycle'); return; // If negative cycle is detected, simply // return } } printArr(dist, V); return; } // Driver's code int main() { /* Let us create the graph given in above example */ int V = 5; // Number of vertices in graph int E = 8; // Number of edges in graph struct Graph* graph = createGraph(V, E); // add edge 0-1 (or A-B in above figure) graph->エッジ[0].src = 0; グラフ->エッジ[0].dest = 1; グラフ->エッジ[0].weight = -1; // エッジ 0 ～ 2 (または上図の A ～ C) を追加します。graph->edge[1].src = 0; グラフ->エッジ[1].dest = 2; グラフ->エッジ[1].weight = 4; // エッジ 1-2 (または上図の B-C) を追加します。graph->edge[2].src = 1; グラフ->エッジ[2].dest = 2; グラフ->エッジ[2].weight = 3; // エッジ 1 ～ 3 (または上図の B ～ D) を追加します。graph->edge[3].src = 1; グラフ->エッジ[3].dest = 3; グラフ->エッジ[3].weight = 2; // エッジ 1 ～ 4 (または上図の B ～ E) を追加します。graph->edge[4].src = 1; グラフ->エッジ[4].dest = 4; グラフ->エッジ[4].weight = 2; // エッジ 3-2 (または上図の D-C) を追加します。graph->edge[5].src = 3; グラフ->エッジ[5].dest = 2; グラフ->エッジ[5].weight = 5; // エッジ 3-1 (または上図の D-B) を追加します。graph->edge[6].src = 3; グラフ->エッジ[6].dest = 1; グラフ->エッジ[6].weight = 1; // エッジ 4-3 (または上図の E-D) を追加します。graph->edge[7].src = 4; グラフ->エッジ[7].dest = 3; グラフ->エッジ[7].weight = -3; // 関数呼び出し BellmanFord(graph, 0); 0を返します。 }>> ジャワ // A Java program for Bellman-Ford's single source shortest // path algorithm. import java.io.*; import java.lang.*; import java.util.*; // A class to represent a connected, directed and weighted // graph class Graph { // A class to represent a weighted edge in graph class Edge { int src, dest, weight; Edge() { src = dest = weight = 0; } }; int V, E; Edge edge[]; // Creates a graph with V vertices and E edges Graph(int v, int e) { V = v; E = e; edge = new Edge[e]; for (int i = 0; i < e; ++i) edge[i] = new Edge(); } // The main function that finds shortest distances from // src to all other vertices using Bellman-Ford // algorithm. The function also detects negative weight // cycle void BellmanFord(Graph graph, int src) { int V = graph.V, E = graph.E; int dist[] = new int[V]; // Step 1: Initialize distances from src to all // other vertices as INFINITE for (int i = 0; i < V; ++i) dist[i] = Integer.MAX_VALUE; dist[src] = 0; // Step 2: Relax all edges |V| - 1 times. A simple // shortest path from src to any other vertex can // have at-most |V| - 1 edges for (int i = 1; i < V; ++i) { for (int j = 0; j < E; ++j) { int u = graph.edge[j].src; int v = graph.edge[j].dest; int weight = graph.edge[j].weight; if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) dist[v] = dist[u] + weight; } } // Step 3: check for negative-weight cycles. The // above step guarantees shortest distances if graph // doesn't contain negative weight cycle. If we get // a shorter path, then there is a cycle. for (int j = 0; j < E; ++j) { int u = graph.edge[j].src; int v = graph.edge[j].dest; int weight = graph.edge[j].weight; if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) { System.out.println( 'Graph contains negative weight cycle'); return; } } printArr(dist, V); } // A utility function used to print the solution void printArr(int dist[], int V) { System.out.println('Vertex Distance from Source'); for (int i = 0; i < V; ++i) System.out.println(i + ' ' + dist[i]); } // Driver's code public static void main(String[] args) { int V = 5; // Number of vertices in graph int E = 8; // Number of edges in graph Graph graph = new Graph(V, E); // add edge 0-1 (or A-B in above figure) graph.edge[0].src = 0; graph.edge[0].dest = 1; graph.edge[0].weight = -1; // add edge 0-2 (or A-C in above figure) graph.edge[1].src = 0; graph.edge[1].dest = 2; graph.edge[1].weight = 4; // add edge 1-2 (or B-C in above figure) graph.edge[2].src = 1; graph.edge[2].dest = 2; graph.edge[2].weight = 3; // add edge 1-3 (or B-D in above figure) graph.edge[3].src = 1; graph.edge[3].dest = 3; graph.edge[3].weight = 2; // add edge 1-4 (or B-E in above figure) graph.edge[4].src = 1; graph.edge[4].dest = 4; graph.edge[4].weight = 2; // add edge 3-2 (or D-C in above figure) graph.edge[5].src = 3; graph.edge[5].dest = 2; graph.edge[5].weight = 5; // add edge 3-1 (or D-B in above figure) graph.edge[6].src = 3; graph.edge[6].dest = 1; graph.edge[6].weight = 1; // add edge 4-3 (or E-D in above figure) graph.edge[7].src = 4; graph.edge[7].dest = 3; graph.edge[7].weight = -3; // Function call graph.BellmanFord(graph, 0); } } // Contributed by Aakash Hasija> Python3 # Python3 program for Bellman-Ford's single source # shortest path algorithm. # Class to represent a graph class Graph: def __init__(self, vertices): self.V = vertices # No. of vertices self.graph = [] # function to add an edge to graph def addEdge(self, u, v, w): self.graph.append([u, v, w]) # utility function used to print the solution def printArr(self, dist): print('Vertex Distance from Source') for i in range(self.V): print('{0} {1}'.format(i, dist[i])) # The main function that finds shortest distances from src to # all other vertices using Bellman-Ford algorithm. The function # also detects negative weight cycle def BellmanFord(self, src): # Step 1: Initialize distances from src to all other vertices # as INFINITE dist = [float('Inf')] * self.V dist[src] = 0 # Step 2: Relax all edges |V| - 1 times. A simple shortest # path from src to any other vertex can have at-most |V| - 1 # edges for _ in range(self.V - 1): # Update dist value and parent index of the adjacent vertices of # the picked vertex. Consider only those vertices which are still in # queue for u, v, w in self.graph: if dist[u] != float('Inf') and dist[u] + w < dist[v]: dist[v] = dist[u] + w # Step 3: check for negative-weight cycles. The above step # guarantees shortest distances if graph doesn't contain # negative weight cycle. If we get a shorter path, then there # is a cycle. for u, v, w in self.graph: if dist[u] != float('Inf') and dist[u] + w < dist[v]: print('Graph contains negative weight cycle') return # print all distance self.printArr(dist) # Driver's code if __name__ == '__main__': g = Graph(5) g.addEdge(0, 1, -1) g.addEdge(0, 2, 4) g.addEdge(1, 2, 3) g.addEdge(1, 3, 2) g.addEdge(1, 4, 2) g.addEdge(3, 2, 5) g.addEdge(3, 1, 1) g.addEdge(4, 3, -3) # function call g.BellmanFord(0) # Initially, Contributed by Neelam Yadav # Later On, Edited by Himanshu Garg> C# // C# program for Bellman-Ford's single source shortest // path algorithm. using System; // A class to represent a connected, directed and weighted // graph class Graph { // A class to represent a weighted edge in graph class Edge { public int src, dest, weight; public Edge() { src = dest = weight = 0; } }; int V, E; Edge[] edge; // Creates a graph with V vertices and E edges Graph(int v, int e) { V = v; E = e; edge = new Edge[e]; for (int i = 0; i < e; ++i) edge[i] = new Edge(); } // The main function that finds shortest distances from // src to all other vertices using Bellman-Ford // algorithm. The function also detects negative weight // cycle void BellmanFord(Graph graph, int src) { int V = graph.V, E = graph.E; int[] dist = new int[V]; // Step 1: Initialize distances from src to all // other vertices as INFINITE for (int i = 0; i < V; ++i) dist[i] = int.MaxValue; dist[src] = 0; // Step 2: Relax all edges |V| - 1 times. A simple // shortest path from src to any other vertex can // have at-most |V| - 1 edges for (int i = 1; i < V; ++i) { for (int j = 0; j < E; ++j) { int u = graph.edge[j].src; int v = graph.edge[j].dest; int weight = graph.edge[j].weight; if (dist[u] != int.MaxValue && dist[u] + weight < dist[v]) dist[v] = dist[u] + weight; } } // Step 3: check for negative-weight cycles. The // above step guarantees shortest distances if graph // doesn't contain negative weight cycle. If we get // a shorter path, then there is a cycle. for (int j = 0; j < E; ++j) { int u = graph.edge[j].src; int v = graph.edge[j].dest; int weight = graph.edge[j].weight; if (dist[u] != int.MaxValue && dist[u] + weight < dist[v]) { Console.WriteLine( 'Graph contains negative weight cycle'); return; } } printArr(dist, V); } // A utility function used to print the solution void printArr(int[] dist, int V) { Console.WriteLine('Vertex Distance from Source'); for (int i = 0; i < V; ++i) Console.WriteLine(i + ' ' + dist[i]); } // Driver's code public static void Main() { int V = 5; // Number of vertices in graph int E = 8; // Number of edges in graph Graph graph = new Graph(V, E); // add edge 0-1 (or A-B in above figure) graph.edge[0].src = 0; graph.edge[0].dest = 1; graph.edge[0].weight = -1; // add edge 0-2 (or A-C in above figure) graph.edge[1].src = 0; graph.edge[1].dest = 2; graph.edge[1].weight = 4; // add edge 1-2 (or B-C in above figure) graph.edge[2].src = 1; graph.edge[2].dest = 2; graph.edge[2].weight = 3; // add edge 1-3 (or B-D in above figure) graph.edge[3].src = 1; graph.edge[3].dest = 3; graph.edge[3].weight = 2; // add edge 1-4 (or B-E in above figure) graph.edge[4].src = 1; graph.edge[4].dest = 4; graph.edge[4].weight = 2; // add edge 3-2 (or D-C in above figure) graph.edge[5].src = 3; graph.edge[5].dest = 2; graph.edge[5].weight = 5; // add edge 3-1 (or D-B in above figure) graph.edge[6].src = 3; graph.edge[6].dest = 1; graph.edge[6].weight = 1; // add edge 4-3 (or E-D in above figure) graph.edge[7].src = 4; graph.edge[7].dest = 3; graph.edge[7].weight = -3; // Function call graph.BellmanFord(graph, 0); } // This code is contributed by Ryuga }> JavaScript // a structure to represent a connected, directed and // weighted graph class Edge { constructor(src, dest, weight) { this.src = src; this.dest = dest; this.weight = weight; } } class Graph { constructor(V, E) { this.V = V; this.E = E; this.edge = []; } } function createGraph(V, E) { const graph = new Graph(V, E); for (let i = 0; i < E; i++) { graph.edge[i] = new Edge(); } return graph; } function printArr(dist, V) { console.log('Vertex Distance from Source'); for (let i = 0; i < V; i++) { console.log(`${i} ${dist[i]}`); } } function BellmanFord(graph, src) { const V = graph.V; const E = graph.E; const dist = []; for (let i = 0; i < V; i++) { dist[i] = Number.MAX_SAFE_INTEGER; } dist[src] = 0; for (let i = 1; i <= V - 1; i++) { for (let j = 0; j < E; j++) { const u = graph.edge[j].src; const v = graph.edge[j].dest; const weight = graph.edge[j].weight; if (dist[u] !== Number.MAX_SAFE_INTEGER && dist[u] + weight < dist[v]) { dist[v] = dist[u] + weight; } } } for (let i = 0; i < E; i++) { const u = graph.edge[i].src; const v = graph.edge[i].dest; const weight = graph.edge[i].weight; if (dist[u] !== Number.MAX_SAFE_INTEGER && dist[u] + weight < dist[v]) { console.log('Graph contains negative weight cycle'); return; } } printArr(dist, V); } // Driver program to test methods of graph class // Create a graph given in the above diagram const V = 5; const E = 8; const graph = createGraph(V, E); graph.edge[0] = new Edge(0, 1, -1); graph.edge[1] = new Edge(0, 2, 4); graph.edge[2] = new Edge(1, 2, 3); graph.edge[3] = new Edge(1, 3, 2); graph.edge[4] = new Edge(1, 4, 2); graph.edge[5] = new Edge(3, 2, 5); graph.edge[6] = new Edge(3, 1, 1); graph.edge[7] = new Edge(4, 3, -3); BellmanFord(graph, 0);> 出力
Vertex Distance from Source 0 0 1 -1 2 2 3 -2 4 1>
Bellman-Ford アルゴリズムの複雑さの分析 :
- グラフ接続時の時間計算量:
- 最良の場合： O(E)、1 回目と 2 回目の緩和後の距離配列が同じ場合、単純にそれ以上の処理を停止できます。
- 平均的なケース: O(V*E)
- 最悪の場合： O(V*E)
- グラフが切断された場合の時間計算量 :
- すべてのケース: O(E*(V^2))
- 補助スペース: O(V)。V はグラフ内の頂点の数です。
Bellman Ford のアルゴリズム アプリケーション:
- ネットワークルーティング: Bellman-Ford は、コンピュータ ネットワーキングでルーティング テーブル内の最短パスを見つけるために使用され、データ パケットがネットワーク間を効率的に移動できるようにします。
- GPS ナビゲーション: GPS デバイスは Bellman-Ford を使用して、場所間の最短または最速のルートを計算し、ナビゲーション アプリとデバイスを支援します。
- 輸送と物流: Bellman-Ford のアルゴリズムを適用すると、輸送および物流における車両の最適な経路を決定し、燃料消費量と移動時間を最小限に抑えることができます。
- ゲーム開発: Bellman-Ford は、さまざまな経路にさまざまなコストや障害物がある可能性があるゲーム開発において、仮想世界内の移動とナビゲーションをモデル化するために使用できます。
- ロボット工学と自動運転車: このアルゴリズムは、障害物、地形、エネルギー消費を考慮した、ロボットや自動運転車の経路計画に役立ちます。
Bellman Ford のアルゴリズムの欠点:
- グラフに負のエッジ サイクルが含まれる場合、ベルマン フォード アルゴリズムは失敗します。
単一ソースの最短パス アルゴリズムに関する関連記事: