C ++のベルマンフォードアルゴリズム？

ベルマンフォードアルゴリズムは、開始頂点として扱われる頂点から計算された頂点の最短経路を見つけるために使用される動的計画法アルゴリズムです。このアルゴリズムは反復法に従い、最短パスを継続的に見つけようとします。重み付きグラフのベルマンフォードアルゴリズム。

このアルゴリズムは、1955年にAlphonsoshimbelによって提案されました。アルゴリズムにはRichardBellmanとLesterFordによる改訂があります。 1956年と1958年に、このアルゴリズムのためにベルマンフォードアルゴリズムと名付けられました。 。このアルゴリズムは、1957年にEward F. Mooreによって改訂され、 Bellman-Ford-Moore Algorithmに名前が付けられました。 。

このアルゴリズムは、負の重みを持つエッジを処理できるため、優れています。アルゴリズムはダイクストラのアルゴリズムよりも低速ですが、より用途の広いタイプのグラフを処理するため、より優れたアルゴリズムです。

アルゴリズム

Input : weighted graph and starting vertex
Output : shortest distance between all vertices from the src.
For negative weight cycle, the same will be returned as the weight cannot be calculated.

アルゴリズム

Step 1 : This is the initialisation step, an array is created that stores the distance of all vertices from the initial vertex. The array say dist[] of size equal to the number of vertices in the graph.
Step 2 : Calculate the shortest distance of vertex. Loop through step 3 for n-1 number of times ( n is the number of vertices of graph).
Step 3 : Follow following steps for each edge i-j
   Step 3.1 : If dist[v] > dist[u] + weight[uv]. Then, dist[v] = dist[u] + weight[uv].
Step 4 : Check and flag if there is any negative cycle. If step 3.1 executes then there is a negative cycle.

負のサイクル：通常のエッジトラバーサルよりも短いパスが存在する場合、負のサイクルがあります。

例

グラフに関連するいくつかの問題を解決して、アルゴリズムについて詳しく学びましょう。

グラフのすべての頂点とエッジ、およびそれらに関連付けられた重みを確認できます。

頂点Aと頂点Eの間の最短距離を見つけましょう ベルマンフォードアルゴリズムを使用します。

ソース頂点（A）をゼロ0に設定し、残りの距離を無限大∞に設定します。

A B C D E
0 ∞ ∞ ∞ ∞

エッジの重量を確認するA-B 次にA-C 、

A-Bの場合はパスが1つだけですが、A-Cの場合は通過できるパスが2つあり、どちらが最短かを確認します。

A B  C D E
0 ∞  ∞ ∞ ∞
0 -2 ∞ ∞ ∞   - for (A-B)
0 -2 3 ∞ ∞   - for (A-C)

次の頂点については、最初の頂点の最短距離を計算します。

A B  C D E
0 ∞  ∞ ∞ ∞
0 -2 ∞ ∞ ∞
0 -2 3 3 10

したがって、アルゴリズムを使用する最短距離は10です。パスを移動する A-B-E 。これを使用して、負のサイクルがあることもわかりました。

例

#include <bits/stdc++.h>
struct Edge {
   int src, dest, weight;
};
struct Graph {
   int V, E;
   struct Edge* edge;
};
struct Graph* createGraph(int V, int E) {
   struct Graph* graph = new Graph;
   graph->V = V;
   graph->E = E;
   graph->edge = new Edge[E];
   return graph;
}
void BellmanFord(struct Graph* graph, int src) {
   int V = graph->V;
   int E = graph->E;
   int dist[V];
   for (int i = 0; i < V; i++)
      dist[i] = INT_MAX;
      dist[src] = 0;
   for (int i = 1; i <= V - 1; 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_MAX && dist[u] + weight < dist[v])
         dist[v] = dist[u] + weight;
      }
   }
   for (int i = 0; i < E; i++) {
      int u = graph->edge[i].src;
      int v = graph->edge[i].dest;
      int weight = graph->edge[i].weight;
      if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
         printf("Graph contains negative weight cycle");
         return;
      }
   }
   printf("Vertex :\t\t\t ");
   for (int i = 0; i < V; ++i)
      printf("%d \t", i);
      printf("\nDistance From Source : ");
   for (int i = 0; i < V; ++i)
      printf("%d \t",dist[i]);
   return;
}
int main() {
   int V = 5;
   int E = 8;
   struct Graph* graph = createGraph(V, E);
   graph->edge[0].src = 0;
   graph->edge[0].dest = 1;
   graph->edge[0].weight = -1;
   graph->edge[1].src = 0;
   graph->edge[1].dest = 2;
   graph->edge[1].weight = 4;
   graph->edge[2].src = 1;
   graph->edge[2].dest = 2;
   graph->edge[2].weight = 3;
   graph->edge[3].src = 1;
   graph->edge[3].dest = 3;
   graph->edge[3].weight = 2;
   graph->edge[4].src = 1;
   graph->edge[4].dest = 4;
   graph->edge[4].weight = 2;
   graph->edge[5].src = 3;
   graph->edge[5].dest = 2;
   graph->edge[5].weight = 5;
   graph->edge[6].src = 3;
   graph->edge[6].dest = 1;
   graph->edge[6].weight = 1;
   graph->edge[7].src = 4;
   graph->edge[7].dest = 3;
   graph->edge[7].weight = -3;
   BellmanFord(graph, 0);
   return 0;
}

出力

Vertex : 0 1 2 3 4
Distance From Source : 0 -1 2 -2 1