[알고리즘 개념] 다익스트라

다익스트라 알고리즘

한 그래프의 특정 시작점에서 다른 모든 정점으로 가는 최단거리를 각각 구해주는 알고리즘을 말한다. 다른 정점까지의 최단 경로를 구하는 과정에서 모든 정점을 탐색하기에 최단 경로를 보장할 수 있다. 단, 가중치가 양수일 때 가능하다.(음수일 땐 벨만포드를 사용하면 된다) 참고로 그래프 알고리즘의 종류 대표적으로 다익스트라, 벨만포드, 플로이드 워셜이 있다.

다익스트라 알고리즘을 어떻게 구현하면 될지 알아보자.

예시로 5개의 정점이 있고 1번 정점에서 출발해 2~5번 정점까지의 최단거리를 구해야 할 때 먼저 입력받은 값을 각각 u(시작 위치), v(도착 위치), w(가중치)라고 한다면 u.append(v,w)가 된다. 만약 V(정점)의 개수가 적다면 위의 인접 리스트 방식이 아닌 인접 행렬을 사용해도 된다.  V의 개수에 영향을 받는 이유는 입력값을 대입할 자료구조는 대표적으로 배열과 리스트가 있는데 V의 개수가 1만을 넘게 된다면 대부분의 문제의 메모리제한 1초(약 1억)을 넘겨버린다.

다음으로 입력받은 정점을 다익스트라 알고리즘을 활용하여 탐색해야 한다. 이 과정을 진행하기 전에 거리를 저장할 배열을 만들어야 한다. 그 다음 거리를 저장할 배열의 초기값을 INF(무한대)로 설정한다. INF로 설정하는 이유는 정수 배열의 초기값은 0인데 특정 정점에서 다른 정점까지의 최단거리를 저장할 배열에 0인 상태로 다익스트라 알고리즘을 실행하게 된다면 이미 최단거리인 0이기에 거리를 구할 수 없다.

 

마지막으로 다익스트라 알고리즘의 핵심을 구현하면 된다.

O(ElogV)의 시간복잡도를 가지는 우선순위큐를 활용하여 (거리, 정점)의 형태로 구현된 코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define MX 105
#define INF 0x7fffffff
vector<pair<int,int>> graph[MX];
int n,m, dist[MX];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;

int main() {
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v,w});
    }
    //거리배열 값 설정
    for(int i = 1; i <= n; i++) dist[i] = INF;
    //시작 정점
    dist[1] = 0;
    pq.push({0,1});


    while(!pq.empty()){
    	//(거리, 정점)
        int cost = pq.top().first;
        int cur = pq.top().second;
        pq.pop();

        for(int i = 0; i < graph[cur].size(); i++){
        	//그래프 기준 첫번째 값은 다음 정점
            int next = graph[cur][i].first;
			//그래프 기준 두번째 값은 가중치
            int ncost = graph[cur][i].second;
            if(dist[next] > dist[cur] + ncost){
                dist[next] = dist[cur] + ncost;
                pq.push({dist[next], next});
            }
        }
    }
    int result = 0;
    for(int i = 1; i <= n; i++){
        if(dist[i] == INF) continue;
        result = max(result, dist[i]);
    }
    cout << result;

    return 0;
}

 

 

 

 

 

 

추천 문제

1753번: 최단경로

1238번: 파티