자료구조와 알고리즘/Graph

Bellman-Ford's Shortest Path

그레이트쪼 2016. 9. 13. 00:36

개요 

  • One source to all destinations에 대한 shortest path 문제이다. Dijkstra와 다른 점은 여기서는 음수 edge가 존재할 수 있다는 것이다. 물론 음수 cycle은 아니다. (만약 negative cycle이 있을 경우 Bellman-Ford는 그 negative cycle의 weight를 반환한다)
  • 또한 Dijkstra 보다 간단하며 분산 시스템에서 동작하기에 더 적합하다. 그리고 time complexity가 O(VE)인데 엄밀히 말하자면 Dijkstra 보다 좋다. 
  • 방법론적으로는 Floyd-Warshall처럼 DP다. 즉, source와 하나의 destination을 잇는 최소 비용 경로는 경유지를 거치거나 거치지 않는 경우 중 최소값을 취하면 된다. 


방법


1) source로부터 모든 vertex들에 대한 거리를 초기화한다. 크기가 vertex 개수인 배열 dist[]를 만든다. 처음엔 자기 자신인 dist[src]는 0이고 나머지 vertex는 모두 infinite이다.


2) V – 1 (vertex 개수보다 하나 작음)만큼 루프를 돌면서 아래의 연산을 한다.

a) 모든 edge u-v (vertex u와 v를 연결하는 edge)에 대해서

b) u까지의 거리에 uv의 weight를 더한 값이 기존 v까지의 거리보다 짧다면 v까지의 거리를 그것으로 갱신한다.

 

3) 부가적으로 negative cycle이 있는지 체크하기 위해서는 아래의 연산을 한다.

a) 모든 edge u-v (vertex u와 v를 연결하는 edge)에 대해서

b) u까지의 거리에 uv의 weight를 더한 값이 기존 v까지의 거리보다 짧다면 negative cycle이 있다고 판단한다.

  • 두 번째 과정을 보자. 최초에는 하나의 edge를 사용하는 최소 거리를 구하고 그 다음은 최대 2개의 edge를 사용하는 최소 거리를 구한다. 이런식으로 최대 vertex개수 - 1만큼의 edge에 대해서 연산을 한다. (왜냐하면 모든 노드까지의 경로에서 최대 edge는 vertex 개수보다 하나 작기 때문)
  • 세 번째 과정은 사실 부가적인 과정이다. 만일 문제에서 negative cycle이 없다는 것이 보장된다면 굳이 할 필요없다. 이 과정이 성립하는 이유는 두 번째 과정에서 이미 최소 거리를 구했다는 가정이 있기 때문이다. 따라서 모든 edge를 한 번 이상 순회하였을 때 어떤 vertex에 대한 path가 짧아진다면 negative cycle이 존재하는 것이다.


예제

  • 소스인 A만 0으로 하고 나머지의 vertex와의 거리는 무제한으로 설정한다. vertex 개수가 5이니 모든 edge는 4번 처리되어야 한다. 

  • Edge가 (B,E), (D,B), (B,D), (A,B), (A,C), (D,C), (B,C), (E,D) 순으로 처리된다고 하자. 첫 번째 순회를 통해 모든 edge에 대해서 거리가 재계산된다. 
  • 아래의 그림에서 첫번째 줄은 초기 거리값이고 두번째 줄은 (B,E), (D,B), (B,D), (A,B)가 처리된 후의 거리이다. 세번째 줄은 (A,C)가 처리된 후이고, 네번째 줄은 (D,C), (B,C), (E,D)가 처리된 후의 거리이다. 

  • 첫번째 순회를 통해서 모든 경로가 많아야 하나의 edge는 거쳐간다는 것이 보장되었다. 이번엔 두번째 순회를 해보자. 아래의 그림과 같다. 

  • 두번째 순회를 통해 모든 경로가 많아야 두개의 edge는 거쳐간다는 것이 보장되었다. 이런식으로 세번째, 네번째 순회를 해나가면 된다. 


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <stdio.h>
 
const int MAX_INT = ~(1 << 31);
 
// A structure to represent a weighted edge in graph
typedef struct {
    int src;
    int dst;
    int weight;
} Edge;
 
// A structure to represent a connected, directed and weighted graph
typedef struct {
    int V; // Number of vertices
    int E; // Number of edges
    Edge* edge; // An pointer of edge array
} Graph;
 
// This function finds shortest distances from src to all other vertices
// using Bellman-Ford algorithm. The function also detects negative weight cycle
void bellmanford(Graph* graph, int src)
{
    int V = graph->V;
    int E = graph->E;
    int* dist = (int*)malloc(sizeof(int) * V);
 
    // Step 1: Initialize distances from src to all other vertices as INFINITE
    for (int i = 1; i < V; i++)
        dist[i] = MAX_INT;
    dist[0] = 0;
 
    // Step 2: Relax all edges |V| - 1 times. A simple shortest path from src
    // to any other vertex can have at-most |V| - 1 edges
    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].dst;
            int weight = graph->edge[j].weight;
            if (dist[u] != MAX_INT && dist[u] + weight < dist[v])
                dist[v] = dist[u] + weight;
        }
    }
 
    // Step 3: check for negative-weight cycles. The above step guarantees
    // shortest distances if graph doesn't contain negative weight cycle.
    // If we get a shorter path, then there is a cycle.
    for (int i = 0; i < E; i++)
    {
        int u = graph->edge[i].src;
        int v = graph->edge[i].dst;
        int weight = graph->edge[i].weight;
        if (dist[u] != MAX_INT && dist[u] + weight < dist[v]) {
            printf("Graph contains negative weight cycle");
            return;
        }
    }
 
    printf("Vertex   Distance from Source\n");
    for (int i = 0; i < V; ++i)
        printf("%d \t\t %d\n", i, dist[i]);
}
 
int main()
{
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = 5; // Number of vertices in graph
    graph->E = 8; // Number of edges in graph
    graph->edge = (Edge*)malloc(sizeof(Edge) * graph->E);
 
    // add edge 0-1 (or A-B)
    graph->edge[0].src = 0;
    graph->edge[0].dst = 1;
    graph->edge[0].weight = -1;
 
    // add edge 0-2 (or A-C)
    graph->edge[1].src = 0;
    graph->edge[1].dst = 2;
    graph->edge[1].weight = 4;
 
    // add edge 1-2 (or B-C)
    graph->edge[2].src = 1;
    graph->edge[2].dst = 2;
    graph->edge[2].weight = 3;
 
    // add edge 1-3 (or B-D)
    graph->edge[3].src = 1;
    graph->edge[3].dst = 3;
    graph->edge[3].weight = 2;
 
    // add edge 1-4 (or A-E)
    graph->edge[4].src = 1;
    graph->edge[4].dst = 4;
    graph->edge[4].weight = 2;
 
    // add edge 3-2 (or D-C)
    graph->edge[5].src = 3;
    graph->edge[5].dst = 2;
    graph->edge[5].weight = 5;
 
    // add edge 3-1 (or D-B)
    graph->edge[6].src = 3;
    graph->edge[6].dst = 1;
    graph->edge[6].weight = 1;
 
    // add edge 4-3 (or E-D)
    graph->edge[7].src = 4;
    graph->edge[7].dst = 3;
    graph->edge[7].weight = -3;
 
    bellmanford(graph, 0);
 
    return 0;
}

  • 라인 44 ~ 56의 step 3는 negative cycle이 없다는 것이 보장되는 문제에서는 굳이 할 필요 없는 과정이다. 
  • 아래는 출력값이다. 

Vertex   Distance from Source

0                0

1                -1

2                2

3                -2

4                1
  • Time complexity는 O(VE)이다. 모든 edge들에 대해서 destination의 값을 갱신한다. 이것을 path의 최대 edge개수 V-1회 반복하기 때문이다. 


저작자표시