다익스트라 알고리즘(최단 경로)

🟩음의 가중치(음의 간선, 음의 값)가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단 거리를 구하는 알고리즘

두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘이지만

한 꼭짓점을 "소스" 꼭짓점으로 고정하고, 그래프의 다른 모든 꼭짓점까지의 최단경로를 찾는 알고리즘으로 최단 경로 트리를 만드는 것으로도 사용

 

🟩 그리디이자 동적계획법

그리디 : 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택

다이나믹 프로그래밍 : 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신

👉 가능한 적은 비용으로 가장 빠르게 해답을 도달하는 경로를 찾아내는 대부분의 문제에 응용된다.

 

🟩 예제

A노드에서 출발하여 F노드로 가는 최단경로를 구하는 문제

S = 방문한 노드들의 집합

d[N] = A -> N까지 계산된 최단 거리

Q = 방문하지 않은 노드들의 집합

확인되지 않은 거리는 전부 초기값을 무한으로 잡는다 예)INF

 

 

출발지와 출발지의 거리는 확인해 볼 필요도 없이 0 👉 d[A] = 0

출발지를 제외한 모든 노드들도 아직 확인되지 않았기에 👉 d[다른 노드] = 무한

Q는 방문하지 않는 노드들의 집합이므로, 초기화할 때는 모든 노드들의 집합이 된다.

S는 방문한 노드가 아직 없으므로 공집합 상태

 

1. 루프를  돌려 이웃 노드를 방문하고 거리를 계산한다.

 

2. 첫 루프 이후의 그래프의 상태가 업데이트되는 방식

 

3. 더 빠른 경로를 발견한 경우, d[C] = 5 -> 4 값 업데이트

 

4. 무한반복 및 결과

목적지가 F였으므로, 거리는 8

 

🟩 구현 방법

1. 인접 행렬, 선형탐색(반복문 이용), O(V^2)

한 번 방문한 배열은 방문할 수 없으므로 방문 여부를 체크할 배열이 필요할 것이고, 각 노드까지의 최소 비용을 저장할 배열이 필요할 것

구현에서 고려할 것은 미방문 지점의 값을 항상 최소의 값으로 갱신하는 것이 목표이기 때문에, 미방문지점은 매우 큰 값으로 초기화하여 처리해주면 된다.

최소 비용을 갖는 노드를 선택하는 과정은 최악의 경우 모든 노드를 확인해야 하고, 이것은 V번 반복하기 때문에, O(V^2)의 시간 복잡도를 갖는다.

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max(); // 무한대를 표현하기 위한 상수

// 최소값 반환 함수
int minDistance(const vector<int>& dist, const vector<bool>& visited) {
    int minDist = INF, minIndex = -1;
    int n = dist.size();

    for (int i = 0; i < n; ++i) {
        if (!visited[i] && dist[i] <= minDist) {
            minDist = dist[i];
            minIndex = i;
        }
    }

    return minIndex;
}

// 다익스트라 알고리즘 함수
vector<int> dijkstra(const vector<vector<int>>& graph, int start) {
    int n = graph.size();
    vector<int> dist(n, INF); // 시작점으로부터의 최단 거리를 저장할 배열
    vector<bool> visited(n, false); // 방문 여부를 저장할 배열

    dist[start] = 0; // 시작점까지의 거리는 0

    // 모든 정점을 방문할 때까지 반복
    for (int count = 0; count < n - 1; ++count) {
        int u = minDistance(dist, visited); // 아직 방문하지 않은 정점 중 최단 거리를 가진 정점 선택
        visited[u] = true; // 해당 정점을 방문했다고 표시

        // 선택된 정점을 통해 갈 수 있는 모든 인접 정점의 최단 거리 갱신
        for (int v = 0; v < n; ++v) {
            if (!visited[v] && graph[u][v] != INF && dist[u] != INF && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    return dist;
}

int main() {
    int n, m; // 노드 수, 간선 수
    cin >> n >> m;

    vector<vector<int>> graph(n, vector<int>(n, INF)); // 인접 행렬로 그래프 표현

    // 간선 정보 입력
    for (int i = 0; i < m; ++i) {
        int u, v, w; // 출발점, 도착점, 가중치
        cin >> u >> v >> w;
        graph[u][v] = w; // u에서 v로 가는 가중치 w의 간선 추가
    }

    int start; // 시작점
    cin >> start;

    vector<int> shortest_distances = dijkstra(graph, start); // 다익스트라 알고리즘 호출

    // 시작점으로부터 모든 정점까지의 최단 거리 출력
    for (int i = 0; i < n; ++i) {
        if (shortest_distances[i] == INF) {
            cout << "INF ";
        } else {
            cout << shortest_distances[i] << " ";
        }
    }
    cout << endl;

    return 0;
}

 

2. 인접 리스트와 힙, 우선순위 큐 이용, O((V+E)logV)

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

// 간선을 표현하는 클래스
class Edge {
public:
    int to;
    int weight;

    Edge(int t, int w) : to(t), weight(w) {}
};

// 우선순위 큐에서 사용할 비교 함수 정의
class Compare {
public:
    bool operator() (const pair<int, int>& a, const pair<int, int>& b) {
        return a.second > b.second;
    }
};

// 다익스트라 알고리즘
vector<int> dijkstra(vector<vector<Edge>>& graph, int start) {
    int n = graph.size();
    vector<int> dist(n, numeric_limits<int>::max()); // 시작점에서의 최단 거리를 저장할 배열
    dist[start] = 0; // 시작점까지의 거리는 0

    priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq; // 우선순위 큐
    pq.push({start, 0}); // 시작점과 거리를 큐에 삽입

    while (!pq.empty()) {
        int u = pq.top().first;
        int d = pq.top().second;
        pq.pop();

        if (d > dist[u]) continue; // 이미 처리된 정점은 스킵

        for (const Edge& e : graph[u]) {
            int v = e.to;
            int w = e.weight;

            // Relaxation
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({v, dist[v]});
            }
        }
    }

    return dist;
}

int main() {
    int n, m; // 노드 수, 간선 수
    cin >> n >> m;

    vector<vector<Edge>> graph(n); // 인접 리스트로 그래프 표현

    // 간선 정보 입력
    for (int i = 0; i < m; ++i) {
        int u, v, w; // 출발점, 도착점, 가중치
        cin >> u >> v >> w;
        graph[u].push_back(Edge(v, w)); // u에서 v로 가는 가중치 w의 간선 추가
    }

    int start; // 시작점
    cin >> start;

    vector<int> shortest_distances = dijkstra(graph, start); // 다익스트라 알고리즘 호출

    // 시작점으로부터 모든 정점까지의 최단 거리 출력
    for (int i = 0; i < n; ++i) {
        if (shortest_distances[i] == numeric_limits<int>::max()) {
            cout << "INF ";
        } else {
            cout << shortest_distances[i] << " ";
        }
    }
    cout << endl;

    return 0;
}

 

🟩 장점

인접 행렬 또는 우선순위 대기열을 사용하여 구현할 수 있어 가능한 모든 경로를 확인하는 무차별 접근 방식보다 효율적

거리뿐 아니라 경로를 추적하도록 알고리즘을 쉽게 수정할 수 있다.

 

🟩 단점

우선순위 대기열을 사용할 때 간선이 많은 그래프의 경우 느려질 수 있다.

그래프와 거리를 저장하려면 많은 양의 메모리가 필요하다.

동일한 거리에 여러 경로가 있는 경우 최상의 경로를 보장하지 않는다.

지형이나 교통 상황과 같은 다른 요소는 고려하지 않는다.