Bellman-Ford 알고리즘

최소 비용으로 출발 정점에서 도착 정점으로 가는 방법을 찾는 것, 근데 간선에 음수가 존재한다.

여기서는 출발 정점 1, 도착 정점 5
먼저 간선을 1번만 사용해서 갈 수 있는 경로가 있다고 가정하고 계산해 보고,

그다음엔 간선을 2번 사용해서 갈 수 있다고 가정하고 또 계산해 본다.
만약 간선을 2번 사용해서 가는 경로가 더 좋다면(dist가 더 작다면) 그 값으로 갱신한다.

이런 식으로 반복.

그럼 이 과정을 몇 번까지 반복하느냐?
정점이 5개라면, 최단 경로에서 사용할 수 있는 간선의 최대 개수는 4개(V-1)이다.
예를 들면 1→2→3→4→5처럼 모든 정점을 한 번씩 거쳐 가는 경우가 간선을 가장 많이 사용하는 경우다.

 

 

음의 사이클이 존재면 안된다는 전제 조건이 있다.

만약 음의 사이클이 없는한, 노드가 5개일 때 간선을 5개 이상 선택할 수 없다.
만약 간선을 5개 이상 사용해 더 좋은 경로가 나온다면, 이는 음의 사이클이 존재한다는 뜻이다.

만약 이 간선이 -3이 아니라 -9라면, 계속 갱신이 발생하게 된다.
그래서 5 → 4 → 3 → … 처럼 같은 경로를 계속 돌게 된다.
이 경우 비용이 계속 줄어들기 때문에, 이는 음의 사이클이 존재한

 

즉, 어떤 한 정점에서 다른 한 정점으로 갈 때 그래프의 정점 수가 n개라면, 가장 많이 간선을 사용하는 것은 n−1개이다.

 

출발 정점은 1번, 도착 정점은 5번으로 설정

초기 상태
초기화는 1번 정점의 비용을 0으로 두고, 나머지 정점들은 모두 무한대로 초기화한다.
각 값은 해당 정점까지 가는 비용

 

표의 1행은 간선을 1번만 사용해서 각 정점으로 갈 수 있는지를 확인한 결과이다.
1→2는 0+5이므로 갱신해 준다.
1→3도 0+4이므로 갱신해 준다.
하지만 3→4는 현재 3의 값이 무한대이므로 무한대+5가 되어 갱신되지 않는다.
4→2, 2→5, 4->5 역시 이전 값이 무한대이므로 마찬가지로 갱신되지 않는다.

간선을 한 개만 사용해서 갈 수 있는 비용은
2번 정점으로 가는 비용 5, 그리고 3번 정점으로 가는 비용 4뿐이다.

 

이번에는 2번째 행은 간선을 2개 사용했을 때
1→2는 다시 계산해도 0+5이므로 갱신하지 않는다.
1→3도 마찬가지로 갱신되지 않는다.

이제 2→3을 보면, 현재 2번 정점의 값은 5이다.
간선을 2개까지 사용하는 단계이므로 5에 -3을 더하면 2가 되고, 기존 값 4보다 작으므로 갱신한다.

다음으로 3→4를 보면, 2+5=7이 되어 기존 무한대보다 작으므로 갱신한다.
4→2는 현재 4번 정점의 값이 무한대이므로 갱신할 수 없다.
2→5는 5+13=18이 되어 기존 무한대보다 작으므로 18로 갱신한다.
4→5는 4번 정점 값이 아직 무한대이므로 갱신되지 않는다.

 

 

 

1->2,1->3도 확인한다. 

즉 벨만–포드 알고리즘은 매 단계마다 모든 간선을 다시 확인한다.

이전 단계에서 갱신된 값이 이번 단계에서 다른 경로의 출발점이 될 수 있기 때문

즉, 벨만–포드는 경로를 따라 이어서 계산하는 방식이 아니라,

매 단계마다 모든 간선을 하나씩 확인하며 거리를 갱신하는 알고리즘이다.

선 2개까지의 최소 비용이 완성

 

이제 간선을 3개 사용했을 때를 확인한다.

1→2는 여전히 비용이 5이므로 갱신할 것이 없다.
1→3은 기존 값이 4인데, 현재 값 2가 더 작으므로 갱신하지 않는다.
2→3 역시 값이 2로 동일하므로 갱신하지 않는다

 

3→4를 보면, 2+5=7이 되어 기존에 저장된 9보다 작으므로 갱신해 준다.
2→5는 값이 같아 갱신하지 않는다.
4→5는 9+7=16이 되어 기존 값보다 작으므로 갱신한다.

처음에 18이었던 값은 1→2→5 경로였지만,
이제는 간선 3개를 사용한 1→3→4→5 경로로 갱신된다.

현재 0, 5, 2, 7, 16은 가장 좋은 값으로 갱신된 상태이다.

마지막으로 간선을 4개 사용했을 때
3→4는 2+5=7 갱신X
4→2는 7+3=10 5보다 크므로 갱신X
4→5는 7+7=14 갱신된다. 

 

즉, 간선을 4개 사용하는 경로인 1→2→3→4→5가 더 좋은 경로가 된다.
따라서 최종 결과는 14를 출력하면 된다.

벨만–포드 알고리즘은 인접 리스트로 그래프를 구성할 필요가 없다.

그냥 간선을 순회하면서 반복적으로 적용하면 된다.

• 정점 기준으로 퍼져나가는 구조가 아니다.
• 간선 리스트가지고 dist 갱신만 하면 충분

 

또한 거리 정보는 1차원 distance 배열로 충분하다.

• 거리 갱신은 이전 결과를 그대로 덮어쓰며 진행할 수 수 있다.

코드

//1️⃣ 간선 정보 입력
vector<Edge> Ed;
scanf("%d %d", &n, &m);
for(i=1; i<=m; i++){
    scanf("%d %d %d", &a, &b, &c);
    Ed.push_back(Edge(a,b,c));
}

//2️⃣ distance 배열 초기화
for(i=1; i<=n; i++){
    dist[i] = 2147000000;
}
scanf("%d %d", &s, &e);
dist[s] = 0;  // 출발 정점은 0으로 초기화

//3️⃣ 최단 거리 갱신 (V-1번 반복)
//i가 1이면 간선을 1번만 사용하는 경우
//i가 2이면 간선을 2번만 사용하는 경우 
for(i=1; i<n; i++){
    for(j=0; j<Ed.size(); j++){
        int u = Ed[j].s;
        int v = Ed[j].e;
        int w = Ed[j].val;

        if(dist[u] != 2147000000 && dist[u] + w < dist[v]){//출발이 무한대이면 하지 않는다. 
		//그리고 출발하는 값에 가중치 더한값이 기존값보다 작으면 값을 갱신해준다.  
            dist[v] = dist[u] + w;
        }
    }
}
//이렇게 하면distance 배열에 최소 비용값이 저장된다. 

//4️⃣ 음의 사이클 검사
//간선을 n번 했을 때 있는지 확인하는 것이다.
for(j=0; j<Ed.size(); j++){
    int u = Ed[j].s;
    int v = Ed[j].e;
    int w = Ed[j].val;

    if(dist[u] != 2147000000 && dist[u] + w < dist[v]){
        printf("-1\n");
    }
}

//5️⃣ 최종 결과 출력
printf("%d\n", dist[e]);

 

 

 

 

 

출처: it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++)