[알고리즘] 다익스트라 + 비교 , 코드

윤경·2022년 1월 16일

TIL algorithm 다익스트라

Algorithm

목록 보기

6/7

다익스트라 알고리즘

다른건 몰라도 다익스트라 알고리즘은 꼭 알고있으라고 했다.

다익스트라 알고리즘(Dijkstra Algorithm)은 음이 아닌 가중 그래프에서 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제를 해결할 수 있다.

원리

다익스트라는 시작 노드부터 각 노드까지의 거리를 저장하는 배열을 이용해 탐색하며 현재 누적 최단 거리와 간선 가중치의 합이 이동하는 노드까지의 저장된 최단 거리보다 작으면 업데이트 시킨다.

그리고 Priority_queue를 이용해 업데이트 된 값을 저장해 늘 최단거리가 짧은 순서부터 탐색하도록 하여 시간 복잡도를 줄일 수 있다.

방문 여부 배열로 이미 방문된 노드를 패스한다.
모든 노드를 방문하거나, 방문하지 않은 노드를 방문할 수 없거나, priority_queue가 비게되면 while문을 종료시킨다.

MST vs 다익스트라

MST: Minimum Spanning Tree로 최소 신장 트리이다.
이는 최소 weight로 모든 노드를 연결하는 것이다.

다익스트라: 정해진 어떤 노드에서 모든 노드까지 최소 경로를 구하는 것이다.

벨만-포드 vs 다익스트라

벨만-포드: 음의 순환이 없는 경우 출발 노드로부터 다른 노드까지의 최단 거리를 산출한다.
그리고 음의 순환 여부 확인이 가능하지만 비교적 오래 걸린다는 단점이 있다.

다익스트라: 모든 간선이 양수이다.
사실상 최단 거리 문제는 다익스트라 알고리즘으로 푼다고 생각하면 된다.

플로이드워셜 vs 다익스트라

플로이드워셜: 모두 때려박아 계산하기 때문에 임의의 두 간선에 대한 최단 경로를 구할 수 있다.
그리고 수행 시간이 오래 걸린다. ➡️ O(N^3)
N 세제곱인 이유는 3중 for문을 이용하기 때문이다. 그래서 수행 시간 측면에서 노드의 개수가 제한적이다.

다익스트라: 출발 노드가 정해진 상태에서 다른 모든 노드로의 최단거리를 산출할 수 있다.
수행 시간이 비교적 적다. ➡️ O(NlogN)
priority_queue를 이용한다.

코드

// 다익스트라 기본 뼈대 코드
// ***** 다익스트라 완전 중요 *****

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

#define INF 987654321

struct Data {
    int node;
    int weight;
    Data() {};
    Data(int node, int weight) : node(node), weight(weight) {};

    // 오름차순 정렬
    bool operator<(const Data d) const {
        return weight > d.weight;
    }
};

using namespace std;

// 10은 참고로 문제에서는 최대 노드 개수만큼 설정
vector<Data> v[10];         // 다음에 방문할 노드, 가중치(priority_queue와 조금 다르긴 한데 여기서는 같이 쓰겠음)
int dist[10];   
bool isVisted[10];
priority_queue<Data> pq;    // 다음에 방문할 노드, 가중치

int N, M;
int a, b, c; // 이렇게 전역으로 선언해두는 것이 좋음

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;  // 노드, 간선

    for(int i=0; i<=N; i++) {   // 초기화
        v[i].clear();
        dist[i] = INF;
        isVisted[i] = false;
    }

    for(int i=0; i<M; i++) {
        cin >> a >> b >> c; 
        v[a].push_back(Data(b, c)); // 단방향일 때는 이 줄만
        v[b].push_back(Data(a, c)); // 양방향일 때는 이렇게 양방향을 구현
    }

    dist[1] = 0;            // 1부터 시작한다고 생각했을 때 출발점을 0으로 초기화
    pq.push(Data(1, 0));    // "1에서 출발하며 그 값은 0이다."

    while(!pq.empty()) {
        Data now = pq.top();            // 지금 방문한 노드 = now
        pq.pop();
        if(isVisted[now.node]) continue; // 방문 했었으면 스킵

        isVisted[now.node] = true;

        // 무조건 이 반복문은 아예 외워두어야 함 
        for(int i=0; i<v[now.node].size(); i++) {   // 현재 방문하는 노드에 연결된 간선 개수만큼 방문해보는 것  
            Data next = v[now.node].at(i);          // 다음 방문하게 될 노드의 정보
            if(dist[next.node] > dist[now.node] + next.weight) {    
                dist[next.node] = dist[now.node] + next.weight;
                pq.push(Data(next.node, dist[next.node]));
            }
        }
    }

    for(int i=0; i<=N; i++) {
        cout << "dist " << i << ": " << dist[i] << "\n";
    }

    return 0;
}