밸만-포드 알고리즘은 다익스트라에서 할 수 없었던 음의 가중치도 계산할 수 있도록 한 방법이다. 그러므로 밸만포드도 다익스트라와 마찬가지로 단일노드 s에서 출발해 그래프 내의 모든 다른 노드에 도착하는 가장 짧은 경로를 찾는 문제이다. 하지만 다익스트라 알고리즘보다 시간복잡도가 높으므로 상황에 맞게 이용해야한다.
밸만-포드 알고리즘은 s와 u사이의 최단 거리를 구할 때, 그래프 내 모든 edge에 대해서 edge relaxation 을 수행해준다.
밸만-포드 알고리즘에서는 모든 엣지에 대한 edge relaxation을 |V|-1회 수행한다.
edge relaxation 이란?
기존의 d(z)가 75였는데 탐색 과정에서 d(u)+e = 60으로 길이가 더 짧을 때, 노드와 엣지의 정보를 업데이트 해주는 것을 말한다.
예시
모든 엣지에 대한 edge relaxation을 1회 수행한 것이다. edge relaxation을 수행할 때 거리 정보 뿐만아니라 최단경로 또한 update합니다.
Negative Cycle
음수 가중치가 사이클을 이루고 있는 경우에는 밸만-포드 알고리즘은 작동하지 않는다.
위의 그림에서 c,d와 e,f가 사이클을 이루고 있는 것을 볼 수 있다. c, d 의 경우에는 사이클을 돌수록 distance가 커져서 최단 경로를 구할 때 문제가 되지 않지만, e,f 의 경우에는 사이클을 돌수록 distance가 작아져서 최단 경로를 구하는 것이 의미가 없어진다.
초깃값 설정을 한다. (시작정점 / 시작정점외 정점들)
edge relaxation : 첫번째 반복을 한다. 최단거리를 찾기위함. (정점의개수(V)-1 번 (모든간선 순회) )
두번째 반복을 한다. 음의사이클 판정하기 위함.
구현
#include<stdio.h>#include<stdlib.h>#include<limits.h>typedefstruct edge{int src, dest, weight;}Edge;typedefstruct graph{// V는 정점의 수 , E는 edge의수int V,E; Edge * edge;}Graph;Graph *create_graph(int V,int E){ Graph * g = (Graph*)malloc(sizeof(Graph));g->V=V; g->E=E;g->edge = (Edge*)malloc((g->E)*sizeof(Edge));return g;}voidprint_array(int dis[],int n){printf("정점\t\t시작점으로부터거리\n");for(int i =0;i<n;i++)printf("%d\t\t\t%d\n",i,dis[i]);}voidbellman(Graph * graph,int src){int v,u,weight;int V =graph->V;int E =graph->E;int distance[V];// 1단계 : 시작점으로 부터 거리 배열을 INT_MAX로 초기화// 단, 출발점에서 출발점으로 거리는 0이다.for(int i=0;i<V;i++) distance[i]=INT_MAX; distance[src]=0;// 2단계 : edge relaxation을 모든 엣지에 대해 |v|-1번 해준다.for(int i=1;i<=V-1;i++){for(int j=0;j<E;j++){ u =graph->edge[j].src; v =graph->edge[j].dest; weight =graph->edge[j].weight;if(distance[u]!=INT_MAX && distance[u]+weight<distance[v]) distance[v] = distance[u]+weight; } }// 3단계 : 음수사이클이 있는지 검사해준다.for(int i=0;i<E;i++){ u =graph->edge[i].src; v =graph->edge[i].dest; weight =graph->edge[i].weight;if(distance[u]!=INT_MAX && distance[u]+weight<distance[v])printf("그래프가 음수 사이클을 포함하고 있습니다.\n"); }print_array(distance, V);}intmain(){int V =5;int E =8; Graph * graph =create_graph(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;bellman(graph,0);return0;}
단점
음수 가중치가 있는 경우 최단 거리를 구할 수 있지만 사이클이 있는 경우에는 작동하지 않는다.