벨만 포드 암호알고리즘 소스 정점에서 모든 정점까지의 최단 경로를 찾는 데 사용됩니다. 음수 또는 양수일 수있는 간선의 가중치와 소스 정점이있는 그래프가 제공됩니다.
이제 독자는 다음과 같이 말할 수 있습니다.
우리는이 Dijkstra 이미. 왜 다른 알고리즘에 신경을 쓰나요? 이러한 쿼리를 Dijkstra의 단점
- 욕심쟁이!
- 음의 가중치로는 작동하지 않습니다.
- 따라서 정답을 제공하거나 제공하지 않을 수 있습니다.
따라서이 기사에서는 다음 사항을 다룹니다.
- Bellman Ford 알고리즘은 어떻게 작동합니까?
- Bellman Ford 알고리즘의 단점.
차례
Bellman Ford Algorithm은 어떻게 작동합니까?
n 개의 정점에 대해 n-1 번 가장자리를 완화합니다. 여기서 n은 가장자리의 수입니다. 이제 살펴 보겠습니다. 이완 방정식 어느 이 알고리즘에서 가장 중요한 것은.
휴식 (u, v) :
if distance (v)> distance (u) + cost (u, v) :
거리 (v) = 거리 (u) + 비용 (u, v)
여기서 u와 v는 모서리입니다.
이제 이완 방정식을 알았으므로 알고리즘을 단계별로 살펴 보겠습니다.
- 소스에서 목적지까지의 거리를 무한대로 초기화합니다.
- 두 가장자리를 선택하고 가장자리 목록을 만듭니다.
- 최단 거리가 자체적으로 반복되거나 최악의 시나리오에서 n-1 회 반복되기 시작할 때까지 가장자리를 이완합니다.
Bellman Ford 알고리즘의 예
예를 들어 이것을 더 잘 이해합시다. 아래 그래프에서 source = 0, number of vertices = 5
처음에 모든 거리를 무한대로 할당하고 가장자리 목록을 만듭니다.
(0,1)에 대해 이완하면 0 + 2 <∞가 있으므로 1의 값을 2로 업데이트합니다. 마찬가지로 모든 가장자리를 이완합니다.
이것은 첫 번째 반복 후에 얻은 그래프입니다.
아래 그래프와 같이 최소 거리를 얻은 최종 그래프에 도달하기 위해 그래프를 5 번 유사하게 처리합니다.
알고리즘이 어떻게 작동하는지 이해 했으므로 이제 코드를 사용하여 구현할 수 있습니다.
Bellman Ford 알고리즘 용 Java 프로그램
import java.util.*;
class bellman
{
public static void bell(int graph[][],int V,int E,int src)
{
int []distance=new int[V];
//Initializing the distance to 1 for all the vertices
for(int i=1;i<V;i++)
distance[i]=Integer.MAX_VALUE;
//Relaxing all the edges V-1 times
for(int i=0;i<V;i++)
{
for(int j=0;j<E;j++)
{ //dist(v)+cost(u,v)<dist(v)
if(distance[graph[j][0]]+graph[j][2]<distance[graph[j][1]])
{
distance[graph[j][1]]=distance[graph[j][0]]+graph[j][2];
}
}
}
//Checking for negative weight cycle
for(int i=0;i<E;i++)
{
int start=graph[i][0];
int desti=graph[i][1];
int cost=graph[i][2];
if(distance[start]!=Integer.MAX_VALUE && distance[start]+cost<distance[desti])
System.out.println("Negative weight cycle detected");
}
for(int i=0;i<V;i++)
{
System.out.println("Shortest distance from 0 to:"+i+" is "+distance[i]);
}
}
public static void main(String args[])
{
int V=5;
int E=7;
int graph[][]={{0,1,2},{0,3,1},{0,2,6},
{1,3,3},{1,4,6},
{2,4,1},
{3,4,5}};
bell(graph,V,E,0);
}
}
C ++ 코드
#include <bits/stdc++.h>
struct Edge
{
int src, dest, weight;
};
struct Graph
{
int V, E;
struct Edge* edge;
};
struct Graph* create(int V, int E)
{
struct Graph* graph = new Graph;
graph->V = V;
graph->E = E;
graph->edge = new Edge[E];
return graph;
}
void chkres(int dist[], int n)
{
printf("Vertex Distance from\n");
for (int i = 0; i < n; ++i)
printf("%d \t %d\n", i, dist[i]);
}
void BellmanFord(struct Graph* graph, int src)
{
int V = graph->V;
int E = graph->E;
int dist[V];
//Initalizing to infinity
for (int i = 0; i < V; i++)
dist[i] = INT_MAX;
dist[src] = 0;
//Relaxing all edges |V| - 1 times.
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;
}
}
chkres(dist, V);
return;
}
int main()
{
int V = 4;
int E = 4;
struct Graph* graph = create(V, E);
graph->edge[0].src = 0;
graph->edge[0].dest = 1;
graph->edge[0].weight = 3;
graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = -2;
graph->edge[2].src = 1;
graph->edge[2].dest = 2;
graph->edge[2].weight = 1;
graph->edge[3].src = 1;
graph->edge[3].dest = 3;
graph->edge[3].weight = 0;
BellmanFord(graph, 0);
return 0;
}
Vertex Distance from 0 0 1 3 2 -2 3 3
복잡성 분석
이 알고리즘의 시간 복잡도는 O (V * E)로 합산됩니다. 여기서 V는 꼭지점의 수이고 E는 그래프.
장점 및 실제 응용
- 음의 가중치에도 적용됩니다. 이것은 경우에 따라 특정 경로를 택하여 이점을 얻을 수있는 곳에서 작동 할 수 있습니다. 예-크리켓 경기에가는 동안 세금을 내야하는 경로와 집에 들르면 돈이나 선물을 줄 수있는 친척의 집이있는 경로가있을 수 있습니다.
- 분산 시스템에 적합
- 그것은 동적 연산
Bellman Ford 알고리즘의 단점
- 유 방향 그래프에서만 작동합니다.
- 지역 정보 만 필요합니다.
