다익스트라 최단 경로 알고리즘(Dijkstra Shortest Path Algorithm)

다익스트라 최단 경로 알고리즘(Dijkstra Shortest Path Algorithm)

• 그래프에서 단일 시작(Single Start) 최단 경로 문제(Shortest Path Problem)
  • 구글 지도 또는 자동차 내비게이션 등에서 경로를 탐색할 때 사용됨.
  • 문제 정의
    • 주어진 그래프 G = <V, E>의 시작 정점(Source Vertex) 과 목적 정점(Destination Vertex) 이 주어질 때, 시작 정점에서 목적 정점까지 이어지는 최소 비용 경로를 구하시오.
      • V : 정점의 집합
      • E : 에지의 집합
      • 각각의 에지는 가중치를 가지고 있음.
• 다익스트라 알고리즘(Dijkstra's Algorithm)
  • 음수 가중치가 없는 그래프에서 동작하는 최단 경로 탐색 알고리즘
  • 프림의 MST 알고리즘을 약간 변경한 형태
• 다익스트라 알고리즘 vs. 프림 알고리즘
  • 프림 알고리즘
    • 경계로부터 최소 거리를 정점의 거리 값으로 설정함.
    • 모든 정점 을 방문해야 종료함.
  • 다익스트라 알고리즘
    • 시작 정점으로부터 각 정점까지의 전체 거리를 사용함.
    • 목적 정점 이 나타나면 종료함.
• 시간 복잡도
  • 피보나치 최소 힙을 사용하여 구현한 다익스트라 알고리즘의 시간 복잡도는 O(E + VlogV)

 

동작 순서

①

• 모든 정점의 거리 값을 무한대 로 초기화함.
• 시작 정점에서 자기 자신까지의 거리는 0이므로, 시작 정점의 거리 값은 0으로 설정함.
• 그리고 모든 거리 값을 최소 힙 H에 추가함.

• 정점 안의 숫자 : 정점 ID
• 정정 옆에 있는 빨간색 숫자 : 현재까지 알려진 시작 정점(1번 정점)에서 각 정점까지의 최소 거리
  • 무한대로 초기화됨.
• 시작 정점은 0으로 초기화 됨.

②

• 최소 힙 H로부터 정점을 하나 꺼냄.
  • 이 정점을 U라고 하면, 정점 U는 시작 정점에서 가장 까운 정점임.
    • 만약 U가 목적 정점이면 최단 경로를 찾은 것이므로 알고리즘을 종료함.

③

• U와 인접한 모든 정점 V에 대해, 만약 V의 거리 값이 (U의 거리 값 + (U, V) 에지 가중치) 보다 크면 V까지 다다르는 더 짧은 경로를 찾은 것으로 볼 수 있음.
  • 그러므로 V의 거리 값을 (U의 거리 값 + (U, V) 에지 가중치) 값으로 설정함.
    • 이러한 과정을 정점 U에 안착했다고 함.

④

• 방문하지 않은 정점이 남아 있다면 ②단계로 이동함.

• 2번 정점에 안착한 후의 그래프 상태
• 4번 정점의 거리 값
  • 2번 정점 거리 값에 (2, 4) 에지 가중치가 더해진 값으로 설정됨.

⑤

• 최소 힙 H로부터 꺼낸 정점이 목적 정점(6번 정점)이면 알고리즘이 종료됨.
• 1번 정점에서 6번 정점까지의 최단 경로

• 각 정점에 나타난 거리 값 : 시작 정점에서 해당 정점까지의 최소 거리

 

코드

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <limits>
#include <algorithm>
using namespace std;

template <typename T>
struct Edge {
    unsigned src;
    unsigned dst;
    T weight;
};

template <typename T>
class Graph {
public:
    // N개의 정점으로 구성되 그래프
    Graph(unsigned N) : V(N) {}

    // 그래프의 정점 개수 반환
    auto vertices() const { return V; }

    // 전체 에지 리스트 반환
    auto& edges() const { return edge_list; }

    // 정점 v에서 나가는 모든 에지를 반환
    auto edges(unsigned v) const {
        vector<Edge<T>> edges_from_v;
        for (auto& e : edge_list) {
            if (e.src == v) {
                edges_from_v.emplace_back(e);
            }
        }

        return edges_from_v;
    }

    void add_edge(Edge<T>&& e) {
        // 에지 양 끝 정점 ID가 유효한지 검사
        if (e.src >= 1 && e.src <= V && e.dst >= 1 && e.dst <= V) {
            edge_list.emplace_back(e);
        }
        else {
            cerr << "에러: 유효 범위를 벗어난 정점!" << endl;
        }
    }

    // 표준 출력 스트림 지원
    template <typename U>
    friend ostream& operator<< (ostream& os, const Graph<U>& G);

private:   
    unsigned V;     // 정점 개수
    vector<Edge<T>> edge_list;
};

template <typename U>
ostream& operator<< (ostream& os, const Graph<U>& G) {
    for (unsigned i = 1; i < G.vertices(); i++) {
        os << i << ":\t";

        auto edges = G.edges(i);
        for (auto& e : edges) {
            os << "{" << e.dst << ": " << e.weight << "}, ";
        }

        os << endl;
    }

    return os;
}

template <typename T>
auto create_reference_graph() {
    Graph<T> G(9);

    map<unsigned, vector<pair<unsigned, T>>> edge_map;
    edge_map[1] = { {2, 2}, {5, 3} };
    edge_map[2] = { {1, 2}, {5, 5}, {4, 1} };
    edge_map[3] = { {4, 2}, {7, 3} };
    edge_map[4] = { {2, 1}, {3, 2}, {5, 2}, {6, 4}, {8, 5} };
    edge_map[5] = { {1, 3}, {2, 5}, {4, 2}, {8, 3} };
    edge_map[6] = { {4, 4}, {7, 4}, {8, 1} };
    edge_map[7] = { {3, 3}, {6, 4} };
    edge_map[8] = { {4, 5}, {5, 3}, {6, 1} };

    for (auto& i : edge_map) {
        for (auto& j : i.second) {
            G.add_edge(Edge<T>{ i.first, j.first, j.second });
        }
    }

    return G;   
}

template <typename T>
struct Label {
    unsigned ID;
    T distance;

    // Label 객체 비교는 거리(distance) 값을 이용
    inline bool operator> (const Label<T>& l) const {
        return this->distance > l.distance;
    }
};

template <typename T>
auto dijkstra_shortest_path(const Graph<T>& G, unsigned src, unsigned dst) {
    // 최소 힙    
    priority_queue<Label<T>, vector<Label<T>>, greater<Label<T>>> heap;

    // 모든 정점에서 거리 값을 최대로 설정
    vector<T> distance(G.vertices(), numeric_limits<T>::max());

    set<unsigned> visited;                            // 방문한 정점
    vector<unsigned> parent(G.vertices());    // 이동 경로를 기억을 위한 벡터

    heap.emplace(Label<T>{src, 0});
    parent[src] = src;

    while (!heap.empty()) {
        auto current_vertex = heap.top();
        heap.pop();

        // 목적지 정점에 도착했다면 종료
        if (current_vertex.ID == dst) {
            cout << current_vertex.ID << "번 정점(목적 정점)에 도착!" << endl;
            break;
        }

        // 현재 정점을 이전에 방문하지 않았다면
        if (visited.find(current_vertex.ID) == visited.end()) {
            cout << current_vertex.ID << "번 정점에 안착!" << endl;

            // 현재 정점과 연결된 모든 에지에 대해
            for (auto& e : G.edges(current_vertex.ID)) {
                auto neighbor = e.dst;
                auto new_distance = current_vertex.distance + e.weight;

                // 인접한 정점의 거리 값이 새로운 경로에 의한 거리 값보다 크면
                // 힙에 추가하고, 거리 값을 업데이트함.
            if (new_distance < distance[neighbor]) {
                heap.emplace(Label<T>{neighbor, new_distance});

                parent[neighbor] = current_vertex.ID;
                distance[neighbor] = new_distance;
                }
            }

            visited.insert(current_vertex.ID);
        }
    }

    // 백트래킹 방식으로 시작 정점부터 목적 정점까지의 경로 구성
    vector<unsigned> shortest_path;
    auto current_vertex = dst;

    while (current_vertex != src) {
        shortest_path.push_back(current_vertex);
        current_vertex = parent[current_vertex];
    }

    shortest_path.push_back(src);
    reverse(shortest_path.begin(), shortest_path.end());

    return shortest_path;
}

int main() {
    using T = unsigned;

    // 그래프 객체 생성
    auto G = create_reference_graph<T>();
    cout << "[입력 그래프]" << endl;
    cout << G << endl;

    auto shortest_path = dijkstra_shortest_path<T>(G, 1, 6);

    cout << endl << "[1번과 6번 정점 사이의 최단 경로]" << endl;
    for (auto v : shortest_path) {
        cout << v << " ";
    }

    return 0;
}

 

결과

[입력 그래프]
1:      {2: 2}, {5: 3},
2:      {1: 2}, {5: 5}, {4: 1},
3:      {4: 2}, {7: 3},
4:      {2: 1}, {3: 2}, {5: 2}, {6: 4}, {8: 5},
5:      {1: 3}, {2: 5}, {4: 2}, {8: 3},
6:      {4: 4}, {7: 4}, {8: 1},
7:      {3: 3}, {6: 4},
8:      {4: 5}, {5: 3}, {6: 1}, 

1번 정점에 안착!
2번 정점에 안착!
5번 정점에 안착!
4번 정점에 안착!
3번 정점에 안착!
8번 정점에 안착!
6번 정점(목적 정점)에 도착!

[1번과 6번 정점 사이의 최단 경로]
1 2 4 6