최단거리 탐색 문제 2
기존의 Dijkstra 알고리즘은 최단거리 탐색에 아주 유용하지만, negative length가 포함되면 사용할 수 없다는 단점이 있다.
이를 보완하기 위해 만들어진 알고리즘으로는 BellmanFord 알고리즘과 FloydWarshall 알고리즘, Johnson's 알고리즘이 있다.
BellmanFord Algorithm
목적
하나의 vertex에서 다른 모든 vertex까지의 최단거리를 계산할 때 쓰는 알고리즘이다. 한 source에서 출발하는 것이 특징이며, negative edge에 대해서도 사용이 가능하다.
알고리즘 설명
기본적인 알고리즘이다.
1) A[i,v]는 source에서 v까지 도착한다고 했을 때, i의 횟수로 갈 수 있는 최단거리이다.
즉, A[0,v]는 v가 source이면 0회 만에 갈 수 있고, 거리는 0이기에 A[0,s]=0, 나머지는 0회만에 도달할 수 없기에 모두 +무한으로 설정한다.
2) i=1,2,...n-1일 때, A[i-1,v]와 모든 vertex w에 대해 A[i-1,w]+l_wv를 비교해 더 짧은 것을 새로운 A[i,v]로 설정한다. (l_wv는 w에서 v까지의 거리, one edge) (n은 vertex number)
만약 i-1번만에 도달한게 여전히 최단거리라면 A[i,v]도 유지, s v1 v2......w v 라는 새로운 경로가 더 짧다면 교체한다. 이는 i-1의 횟수로 도달한 최단거리보다 i의 횟수(1회 증가)를 소비하며 만든 새로운 거리가 더 짧다는 것이다.
3) 이를 반복하며 n-1까지 찾는다. 만약 negative cycle이 없다면 최종 결과를 출력한다.
시간 복잡도는 O(VE)로 Dijkstra보다는 느리지만 유용하다.
여기서 눈 여겨볼 것이 몇 가지 있다.
최적화
먼저 더 빨리 끝낼 수 있는 방법이 있다.
만약 모든 vertex v에 대해 A[j,v]=A[j-1,v]라는 말은, 1회 더 한다 한들 어떠한 업데이트도 없다는 것이다.
즉, 앞으로 횟수를 늘리는 것과는 무관하게 계속 이 거리가 유지된다.
따라서 일찍 프로그램을 종료해도 된다.
Negative Cycle 체크
또 우리는 negative cycle 유무를 체크해야 한다. negative cycle이란, 한 cycle을 돌 때 거리의 합이 음수인 cycle을 의미한다.
positive cycle은 돌면 돌수록 거리가 추가되어 의미가 없지만, negative cycle은 거리를 무한히 작게 만들 수 있어 체크해줘야 한다.
바로 A[n,v]와 A[n-1,v]를 비교하는 것이다.
앞서 i=1,2,..n-1이었는데, 왜 하필 n-1일까?
n은 vertex number이다. source에서 destination까지 최대로 통과하는 vertex가 몇 개일까?
source를 제외하면 n-1이다. 즉 cycle을 돌지 않는다면 n-1개의 vertex만 고려해줘도 충분하다.
그런데, A[n,v]<A[n-1,v]라는 말은, n-1이 최단거리가 아니라는 뜻이다.
이 말은 cycle을 돌며 거리가 줄었고(비둘기 집의 원리), 따라서 negative cycle이 존재한다는 말이다.
이 방식으로 체크하면 빠르게 negative cycle을 체크할 수 있다.
BellmanFord Algorithm 구현
// struct Edge, contains source(from), destination(to), and value of edge
typedef struct _Edge
{
int src;
int dest;
int value;
// from src to dest with value.
} Edge;
//BellmanFord function, input is vertex and edge number, edge's information, and souce node
void BellmanFord(int V, int E, Edge* edge, int src)
{
int *d = (int *)malloc((V+1)*sizeof(int));
int *predecessor = (int *)malloc((V+1)*sizeof(int)); // save path
int **path = malloc(sizeof(int *)*(V+1)); // path array
for(int i=1; i<=V; i++)
{
path[i]=malloc(sizeof(int)*(V+1));
}
for(int i=1; i<=V; i++)
{
for(int j=1; j<=V; j++)
{
path[i][j] = 0;
}
}
// set initial distance
for(int i=1; i<=V; i++)
{
if(i!=src)
{
d[i]=INT_MAX;
predecessor[i]=0; // initialize before path as 0
}
else
{
d[i]=0;
predecessor[i]=-1; // if meet -1, pause
}
}
int sum = 0;
// distance update
for(int i=1; i<=V; i++) // at lecture, i=1,2,...n-1 , and check negative cycle at i=n
{
for(int j=0; j<E; j++) // check every Edge
{
int s = edge[j].src;
int v = edge[j].dest;
int w = edge[j].value;
if(d[s]!=INT_MAX) // if distance is not infinite
{
if(d[s]+w<d[v]) // if weight plus is minimum
{
if(i!=V)
{
d[v]=d[s]+w; // change value
predecessor[v]=s; // previous path save
sum++;
}
else
{
negativeCycle = 1; // set there is negative cycle
return; // exit function
}
}
}
}
if(sum==0) // check if all A[n, i]=A[n, i-1] because sum=0 when there is no change
{
break; // optimization, we can pause if there is no update
}
sum=0;
}
for(int i=1; i<=V; i++) // to make path array
{
for(int j=V; j>=1; j--)
{
if(j==V)
{
path[i][j]=i;
}
else
{
if(predecessor[path[i][j+1]==-1]) // use predecessor for previous node
{
break;
}
path[i][j]=predecessor[path[i][j+1]];
}
}
}
if(negativeCycle != 1)
{
for(int i=1; i<=V; i++)
{
if(i!=src)
{
if(d[i]!=INT_MAX) // if d=inf, just print path: none
{
printf("%d %d length: %d path:", src, i, d[i]);
for(int j=1; j<=V; j++)
{
if(path[i][j]!=0 && path[i][j]!=-1)
{
printf(" %d", path[i][j]);
}
}
printf("\n");
}
else
{
printf("%d %d length: inf path: none\n", src, i);
}
}
}
}
return;
}단순히 구현만 한다면 아주 간단하게 쓸 수 있지만, path까지 출력해주기 위해 predecessor를 사용했다. Lecture 알고리즘을 거의 그대로 구현했다.
