Bellman Ford Algorithm은 시작 정점으로 취급되는 정점에서 계산된 정점의 최단 경로를 찾는 데 사용되는 동적 프로그래밍 알고리즘입니다. 이 알고리즘은 반복적인 방법을 따르며 지속적으로 최단 경로를 찾으려고 합니다. 가중 그래프의 Bellman Ford 알고리즘.
이 알고리즘은 1955년 Alphonso shimbel에 의해 제안되었습니다. 알고리즘에는 Richard Bellman과 Lester Ford가 수정했습니다. 1956년과 1958년에 이 알고리즘으로 인해 Bellman Ford Algorithm이라는 이름이 지정되었습니다. . 이 알고리즘은 1957년 Eward F. Moore에 의해 수정되어 Bellman-Ford-Moore Algorithm이라는 이름이 되었습니다. .
이 알고리즘은 음수 가중치로 가장자리를 처리할 수 있으므로 더 좋습니다. 알고리즘은 Dijkstra의 알고리즘보다 느리지만 더 다양한 유형의 그래프를 처리하므로 더 좋습니다.
알고리즘
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.
Negative Cycle :일반 edge traversal보다 짧은 경로가 존재하면 음의 사이클이 있습니다.
예시
몇 가지 그래프 관련 문제를 해결하여 알고리즘에 대해 자세히 알아보겠습니다.
그래프의 모든 정점과 가장자리와 관련된 가중치를 볼 수 있습니다.
정점 A와 정점 E 사이의 최단 거리를 구합니다. Bellman-ford 알고리즘을 사용합니다.
소스 정점(A)을 0으로 설정하고 나머지 거리를 무한대 ∞로 설정합니다.
A B C D E 0 ∞ ∞ ∞ ∞
모서리 A-B의 가중치 확인 그리고 A-C ,
A-B의 경우 경로가 하나뿐이지만 A-C의 경우 통과할 수 있는 두 개의 경로가 있으며 어느 경로가 가장 짧은지 확인합니다.
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