다익스트라 알고리즘

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

다익스트라 알고리즘은 단일 시작점 최단 경로 알고리즘으로, 시작 정점 s에서부터 다른 정점들까지의 최단 거리를 계산한다. 다익스트

라 알고리즘은 너비 우선 탐색과 유사한 형태를 가진 알고리즘으로 가까운 순서대로 정점을 방문해 가지만 가중치가  있는 그래프에서는 

너비 우선 탐색을 그대로 적용할 수 없다. 너비 우선 탐색은 각 정점을 발견한 순서대로 방문하지만 다익스트라 알고리즘은 더 늦게 발견

한 정점이라도 더 먼저 방문할 수 있어야 한다.

코드 ( C++ )

// 우선순위 큐를 이용해서 구현한 다익스트라 알고리즘

#include <iostream>

#include <vector>

#include <algorithm>

#include <queue>

using namespace std;

const int MAX_V = 100;

const int INF = 987654321;

// 정점의 개수

int V;

// 그래프의 인접 리스트 ( 연결된 정점 번호, 간선 가중치) 쌍을 담는다.

vector<vector<pair<int, int>>> adj;

vector<int> dijkstra(int x)

{

vector<int> dist(V, INF);

dist[x] = 0;

priority_queue<pair<int, int>> pq;

pq.push(make_pair(0,x));

while(!pq.empty()) {

// 거리가 작은 정점부터 꺼내지도록 하자.

int cost = -pq.top().first;

/* = priority_queue<pair<int,int>, vector<pair<int,int>>,

greater<pair<int,int>>> pq; */

int here = pq.top().second;

pq.pop();

// 지금 꺼낸 것보다 더 짧은 경로를 알고 있다면 지금 꺼낸 것을 무시한다.

if (dist[here] < cost) continue;

// 인접한 정점들을 모두 검사한다.

for (int i = 0; i < adj[here].size(); ++i)

{

int there = adj[here][i].first;

int NextDist = cost + adj[here][i].second;

// 더 짧은 경로를 발견하면, dist[]를 갱신하고 우선순위 큐에 넣는다.

if (dist[there] > NextDist)

{

dist[there] = NextDist;

pq.push(make_pair(-NextDist, there));

}

}

}

return dist;

}

int main()

{

V = 7;

  adj = vector<vector<pair<int, int>>>(V, vector<pair<int, int>>());

adj[0].push_back(make_pair(1,5));

adj[0].push_back(make_pair(2, 1));

adj[1].push_back(make_pair(0, 5));

adj[1].push_back(make_pair(3, 1));

adj[1].push_back(make_pair(6, 3));

adj[1].push_back(make_pair(5, 3));

adj[2].push_back(make_pair(0, 1));

adj[2].push_back(make_pair(3, 2));

adj[3].push_back(make_pair(2, 2));

adj[3].push_back(make_pair(1, 1));

adj[3].push_back(make_pair(4, 5));

adj[3].push_back(make_pair(5, 3));

adj[4].push_back(make_pair(3, 5));

adj[5].push_back(make_pair(1, 3));

adj[5].push_back(make_pair(6, 2));

adj[5].push_back(make_pair(3, 3));

adj[6].push_back(make_pair(5, 2));

adj[6].push_back(make_pair(1, 3));

vector<int> ans = dijkstra(0);

// dist에 저장된 각 정점들에 최단거리 출력

for (int i = 0; i < ans.size(); ++i)

cout << "[" << i << "]";

cout << endl;

for (int i = 0; i < ans.size(); ++i)

cout << " " << ans[i] << " ";

cout << endl;

return 0;

}

* 참고 책  : 알고리즘 문제 해결 전략