Shortest path (최단 경로)

최단 경로 문제

    - 그래프 이론에서 두 정점을 잇는 가장 짧은 경로를 찾는 문제

 

 

 

문제 종류

    - 단일-쌍 최단 경로 문제 : V에서 V'로 가는 경로들 중 최단 경로 찾기

    - 단일-출발 최단 경로 문제 : V에서 출발하여 그래프 내의 모든 정점에 도착하는 최단 경로 찾기

    - 단일-도착 최단 경로 문제 : 그래프 내의 모든 정점에서 출발하여 V에 도착하는 최단 경로 찾기

    - 전체-쌍 최단 경로 문제 : 그래프 내의 모든 정점 사이의 최단 경로 찾기

 

 

 

알고리즘 종류

1) Dijkstra algorithm (다익스트라 알고리즘)

    - 그래프 이론에서 하나의 시작 정점에서 다른 모든 정점으로 가는 최단 경로를 찾는 알고리즘

 

    - 동작

        * 출발 노드 선택

        * U노드로 이동할 때, 현재 이동해서 U까지 온 비용과 이전에 저장된 U까지 온 비용을 비교하여 최소 비용을 U노드까지 오는 비용으로 저장

        * 다른 인접 노드로 이동

 

    - 예시

 

 

        * 출발 노드로 A를 선택

 

 

        * 배열에 저장된 비용 중에 아직 방문하지 않았고 비용이 가장 적은 B 노드 선택

        * 노드 B를 거쳐서 모든 노드에 도착하는 비용 VS 이미 저장된 비용 하여 최소 비용을 저장

            + 노드 D의 경우

                ~ 노드 B를 거쳐가는 경우 : 7 + 15 = 22

                ~ 이미 저장된 비용 : INF

                ~ 22가 더 비용이 작으므로 A->D로 가는 비용을 22로 변경

 

 

        * 배열에 저장된 비용 중에 아직 방문하지 않았고 비용이 가장 적은 C 노드 선택

        * 노드 C를 거쳐서 모든 노드에 도착하는 비용 VS 이미 저장된 비용 하여 최소 비용을 저장

            + 노드 D의 경우

                ~ 노드 C를 거쳐가는 경우 : 9 + 11 = 20

                ~ 이미 저장된 비용 : 22

                ~ 20가 더 비용이 작으므로 A->D로 가는 비용을 20로 변경

            + 노드 F의 경우

                ~ 노드 C를 거쳐가는 경우 : 9 + 2 = 11

                ~ 이미 저장된 비용 : 14

                ~ 11이 더 비용이 작으므로 A->F로 가는 비용을 11로 변경

 

 

        * 배열에 저장된 비용 중에 아직 방문하지 않았고 비용이 가장 적은 F 노드 선택

        * 노드 F를 거쳐서 모든 노드에 도착하는 비용 VS 이미 저장된 비용 하여 최소 비용을 저장

            + 노드 E의 경우

                ~ 노드 F를 거쳐가는 경우 : 11 + 9 = 20

                ~ 이미 저장된 비용 : INF

                ~ 20가 더 비용이 작으므로 A->E로 가는 비용을 20로 변경

 

 

        * 배열에 저장된 비용 중에 아직 방문하지 않았고 비용이 가장 적은 F 노드 선택

        * 노드 F를 거쳐서 모든 노드에 도착하는 비용 VS 이미 저장된 비용 하여 최소 비용을 저장

            + 최소 비용 변경 없음

 

 

    - 구현

        * 전체 그래프를 2차 배열에 저장하게 되면 정점을 모두 순회하기 때문에 시간복잡도 O(N^2)을 가짐

        * 정점 선택 기준은 최소 비용이었으므로 최소 힙을 이용하여 데이터를 저장하면 시간복잡도 O(N*logN)을 가짐

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int n = 6; // 정점의 개수  
int INF = 987654321;
 
 
vector<pair<int, int> > edges[9]; // 간선 정보  
int distance[10]; // 간선 비용
 
 
void dijkstra(int start){
    
    //자기 자신까지 비용은 0 
    distance[start] = 0;
    
    // 힙 구조
    priority_queue<pair<int, int> > pq;
    
    // 정점과 비용을 저장  
    pq.push({start, 0})
    
    while(!pq.empty()){
        
        int cur_node = pq.top().first;
        // 힙에는 최소값이 먼저 오도록 하기 위해서
        // -1를 곱해서 저장된 상태
        // 따라서 꺼낼 때는 다시 -1을 곱하여 양수화  
        int cur_distance = -pq.top().second; 
        pq.pop();
        
        // 이미 저장된 거리가 더 최소 비용이면 스킵  
        if(distance[cur_node] < cur_distance) continue;
        
        // 선택한 현재 노드와 연결된 인접 노드들 순회  
        for(int i=0; i<edges[cur_node].size(); i++){
            
            // 선택한 노드의 인접 노드  
            int next_node = edges[cur_node][i].first;
            // 선택한 노드를 거쳐 인접 노드로 가는 비용  
            int next_distance = distance + edges[cur_node][i].second;
            
            // 이미 저장된 최소 비용보다 더 최소 비용이면 저장  
            if(next_distance < distance[next_node]){
                distance[next_node] = next_distance;
                pq.push({next_node, -next_distance});
            }
        }
    }
}
 
 
int main(void){
    
    //초기화 
    for (int i=1; i<=n; i++) 
        distance[i] = INF;
    
    edges[1].push_back({2,7});
    edges[1].push_back({3,9});
    edges[1].push_back({6,14});
    
    edges[2].push_back({1,7});
    edges[2].push_back({3,10});
    edges[2].push_back({4,15});
    
    edges[3].push_back({1,9});
    edges[3].push_back({2,10});
    edges[3].push_back({4,11});
    edges[3].push_back({6,2});
    
    edges[4].push_back({2,15});
    edges[4].push_back({3,11});
    edges[4].push_back({5,6});
    
    edges[5].push_back({4,6});
    edges[5].push_back({6,9});
    
    edges[6].push_back({1,14});
    edges[6].push_back({3,2});
    edges[6].push_back({5,9});
     
    dijkstra(1);
    
    // 결과 보기
    for(int i=1; i<=n; i++)
        printf("%d", distance[i]); 
    
}

    - 시간복잡도

        * 힙 구조에 데이터를 저장하면, O(N * logN)

        * 2차원 배열에 데이터를 저장하면, O(N^2)

 

 

 

2) Floyd-Warshall (플로이드-와셜 알고리즘)

    - 그래프 이론에서 모든 정점에서 다른 모든 정점으로 가는 최단 경로를 찾는 알고리즘

 

    - 동작

        * 거쳐갈 정점 선택

        * U 노드를 거쳐서 갈 때의 비용 VS U 노드를 거쳐서 가지 않을 때 비용

 

    - 예시

 

 

        * 정점 E에서 A를 거쳐 B로 가는 비용은 21(14+7)이므로 INF보다 작기 때문에 갱신

 

        * 정점 A에서 B를 거쳐 C로 가는 비용은 22(7+15)이므로 INF보다 작기 때문에 갱신

        * 정점 A에서 B를 거쳐 E로 가는 비용은 28(7+21)이므로 INF보다 작기 때문에 갱신

        * 이하 같은 방식

 

        * 이하 같은 방식으로 갱신

 

 

    - 구현

#include <stdio.h>
 
using namespace std;
 
int n = 5;
int INF = 987654321;
 
int mat[5][5]= {
        {0, 7, INF, INF, INF},
        {INF, 0, 15, INF, 21},
        {INF, INF, 0, 6, INF},
        {11, 3, INF, 0, INF},
        {14, INF, 13, 9, 0}
    };
 
void FW(){
    
    for(int k=0; k<n; k++){
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                
                if(mat[i][k] + mat[k][j] < mat[i][j])
                    mat[i][j] = mat[i][k] + mat[k][j];
                
            }
        }
    }
    
}
 
int main(void){
    
    FW();
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            printf("%3d ", mat[i][j]);
        }
        printf("\n");
    }
}

 

    - 시간복잡도

        * 정점을 3개의 for문으로 순회하기 때문에 O(N^3)

 

 

참고

    - 블로그 1

    - 블로그 2

    - 위키피디아

    - 블로그 3

    - 블로그 4

    - 위키피디아