그래프 알고리즘 - (3) Dijkstra, Bellman-Ford, Floyd-Warshall

이 글은 포스텍 오은진 교수님의 알고리즘(CSED331) 강의를 기반으로 재구성한 것입니다.

 

세 알고리즘 모두 '최단 거리'를 알아내는 알고리즘이다. 다만 어디서부터 어디까지 알아내는가가 다를 뿐이다.

 

1. dijkstra : O((|V| + |E|) * log|V|)

 한 vertex에서 다른 모든 vertex까지의 최단거리를 알아내는 알고리즘이다. BFS와 유사한 알고리즘으로, BFS는 queue를 사용하지만 dijkstra는 priority queue(heap)을 사용한다. 다만 dijkstra는 weight가 음수인 경우에는 풀리지 않는다!

procedure dijkstra(G, s)
    for all vertex u in V do
        dist(u) = INF
        prev(u) = null
    end for
    
    dist(s) = 0
    H = makeHeap(V)
    while H is not empty do
        u = deleteMin(H)
        for all edges (u, v) in E do
            if dist(v) > dist(u) + weight(u, v) then
                dist(v) = dist(u) + weight(u, v)
                prev(v) = u
                decreaeKey(H, v)
            end if
        end for
    end while
    
// makeHeap(V) : 모든 vertex로 priority queue를 생성
// deleteMin(H) : priority queue의 제일 작은 key를 가지는 element를 pop
// decreaseKey(H, v) : priority queue의 v에 해당하는 key를 갱신

• 핵심은 edge (u, v)에 대해 dist(v) > dist(u) + weight(u, v)라면 dist(v)를 dist(u) + weight(u, v)로 설정하는 것이다.​

 

Time Complexity of dijkstra

 위 pseudo code에도 작성되어 있지만 제일 처음 dist(u)를 설정하는 과정에서 O(n), queue의 deletemin은 n time, decreasekey가 |E| time. 보통 priority queue는 binary tree를 이용하기 때문에 deletemin, insert, decreasekey은 O(log|V|)이기 때문에 O((|V| + |E|)log|V|)라고 기억하면 된다.

 

 

코드 : O((|V| + |E|) * log|V|)

struct mycomp{
    bool operator()(pii&a, pii&b){
        return a.second > b.second; // weight가 큰 것을 앞으로
    }
};
 
// edges[i] : i가 edge의 시작인 edge list
// edges[i][0].first : edge list의 edge end
// edges[i][0].second : edge list의 edge weight
vector<int> dijkstra(int start, vector<vector<pii>> edges){
    // dist initialize
    vector<int> dist(V+1, INF);
    dist[start] = 0;
    
    // heap initialize
    priority_queue<pii, vector<pii>, mycomp> pq;
    pq.push({start, 0});
    
    while(!pq.empty()){
        int cur = pq.top().first;
        int cur_weight = pq.top().second;
        pq.pop();
 
        // 같은 경로지만 cost가 다른 경우를 대비해 아래 로직 넣음
        if(dist[cur] < cur_weight) continue;
        
        // pq.top()에 연결된 모든 edge에 대해 dijkstra 수행
        for(pii &adjs : edges[cur]){
            int adj = adjs.first, adj_weight = adjs.second;
            
            // 만약 갱신 가능하다면 dist 갱신 이후 pq에 다시 넣음
            if(dist[adj] > dist[cur] + adj_weight){
                dist[adj] = dist[cur] + adj_weight;
                pq.push({adj, dist[adj]});
            }
        }
    }
    return dist;
}

 

 

 

2. Bellman-Ford : O(|V| * |E|)

 dijkstra는 negative weight edge가 존재하면 풀리지 않는다. 이런 경우를 해결하기 위해 bellman-ford 알고리즘이 나왔으며, 음수 사이클이 존재하는 경우에는 풀 수 없다.(계속 값이 갱신되기 때문) dijkstra의 더 큰 버전이니만큼 한 vertex부터 다른 모든 vertex까지의 최단거리를 구한다.

 음수 사이클이 존재하는지의 여부는 V번째 for문에서 값이 갱신되는지 여부로 알 수 있다. bellman-ford 알고리즘의 특성상 V-1번째 for문에서 모든 vertex까지의 최단거리가 나오는데, V번째 cycle에서 또 갱신된다면 음수 cycle이 있기 때문이다.

bellman-ford 알고리즘이 V-1번째 for문에서 모든 vertex까지의 최단거리가 결정되나?

proof) 
 vertex가 V개일 때, path π의 최장 길이는 V일 것이다. 한편 시작 vertex가 s일 때 dist[s]는 0인 것을 이미 알고 있다. 그러면 path π에서 s 다음에 있는 것을 w, w', w'', ...라고 두었을 때 dist[w]는 1번의 순회로 알 수 있고 dist[w']는 2번의 순회로 최단거리를 알 수 있다. 귀납적으로, path π의 제일 마지막 vertex x는 V-1번의 순회로 최단거리를 알 수 있다.

 만약 이 과정에서 같은 vertex v를 2번 이상 반복한다면 그 cycle은 negative weight를 가지게 된다. 그렇지 않다면 weight가 더 증가하기 때문에 v를 2번 이상 반복할 이유가 없기 때문이다. 다르게 표현하면 v를 2번 이상 반복하는 것이 없는 경우 V-1번의 순회로 모든 vertex까지 최단거리를 알 수 있다.

 이렇게 V-1번의 순회로 모든 vertex까지 최단거리를 구했다. 만약 V번째 순회로 dist[x]가 갱신된다면 그 중간에 negative weight cycle이 있다는 것이다.

• 핵심은 dist[from]이 INF가 아닐 때만 검사해야 한다.

 

 

코드 : O(|V| * |E|)

// edges[i] : i가 edge의 시작인 edge list
// edges[i][0].first : edge list의 edge end
// edges[i][0].second : edge list의 edge weight
vector<int> bellman_ford(int start, vector<vector<pii>> edges){
    vector<long long> dist(V.size(), INF);
    dist[start] = 0;
    
    // V-1번 순회
    for(int i = 0; i< V.size() - 1; i++){
        // 모든 vertex에 대해
        for(int v = 0; v < V.size(); v++){
            // v의 모든 edge에 대해
            for(pii edge : edges[v]){
                int from = v, to = edge.first, weight = edge.second;
                // dist[from]이 INF이면 갱신이 이상하게 될 수도 있음
                if(dist[from] == INF) continue;
                dist[to] = min(dist[to], dist[from] + edge.second);
            }
        }
    }
    
    bool hasNegCycle = false;
    for(int v = 0; v < V.size(); v++){
        for(pii edge : edges[v]){
            int from = v, to = edge.first, weight = edge.second;
            if(dist[from] == INF) continue;
            if(dist[to] > dist[from] + weight){
                hasNegCycle = true;
                break;
            }
        }
    }
    
    if(hasNegCycle) return {-1};
    else return dist;
}

 

 

 

3. Floyd-Warshall : O($|V|^{3}$)

 floyd-warshall은 모든 점에서 모든 점까지의 최단거리를 구한다.

 아래 코드 중 dist는 2차원 배열이며, dist[i][j]는 vertex i에서 vertex j까지 거리이다.

vector<int> V; // V는 vertex vector
vector<vector<int>> dist(V.size(), vector<int>(V.size(), INF)); // dist[i][j] : distance of vertex i to vertex j
for(int i = 0; i<V.size(); i++){
    dist[i][i] = 0;
}
 
for(int temp = 0; temp < V.size(); temp++){
    for(int from = 0; from < V.size(); from++){
        for(int to = 0; to < V.size(); to++){
            dist[from][to] = min(dist[from][temp] + dist[temp][to], dist[from][to]);
        }
    }
}

 

 

 

4. Dijkstra vs Bellman-Ford vs Floyd-Warshall

dijkstra	bellman-ford	floyd-warshall
한 점부터 다른 모든 점까지	한 점부터 다른 모든 점까지	모든 점부터 다른 모든 점까지
negative weight edge가 있을 시 사용 불가	negative weight edge가 있어도 사용 가능	negative weight cycle이 있으면 사용 불가