1. 다익스트라

• 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘
• 특정한 하나의 정점에서 모든 정점으로 가는 최단 경로를 알려줌
• 음의 간선을 포함할 수 없음

2. 알고리즘

• 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용
• 적용 과정
  1) 출발 노드를 설정
  2) 출발 노드를 기준으로 각 노드의 최소 비용을 저장
  3) 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택
  4) 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려해 최소비용을 갱신
  5) 위 과정에서 3~4번을 반복

3. 코드

1) 배열 사용

int getSmallIndex()
{
	int min = INF;	//INF = 10000000 로 설정
    int index = 0;
    for(int i=0; i<num; i++)	//num은 정점 개수
	{
    	if(d[i]<min && !v[i]) 	//v는 방문 유무, d는 거리
        {
        	min = d[i];
            index = i;
        }
    }
    return index;
}

void dijkstra(int start)
{
	for(int i=0; i< num; i++)
    {
    	d[i] = a[start][i];
    }
    v[start] = true;
    for(int i=0; i<num-2; i++)
    {
    	int current = getSmallIndex();
        v[current] = true;
        for(int j=0; j<6; j++)
        {
        	if(!v[j]){
                d[j] = min(d[j],d[current] + a[current][j]);
            }
        }
    }
}

2) 우선순위 큐

#include <iostream>
#include <vector>
#include <queue>
#define INF 10000000

using namespace std;

int N;
vector<pair<int, int>> a[N+1];
int d[N+1];

void dijkstra(int start)
{
	d[start] = 0;
    priority_queue<pair<int, int>,vector<pair<int, int>>,greator<pair<int, int>>> pq;
    pq.push(make_pair(start,0));
    
    while(!pq.empty())
    {
    	int cur = pq.top().first;
        int dist = pq.top().second;
        pq.pop();
        
        //최단 거리가 아니면 skip
        if(d[cur] < dist) continue;
        for(int i=0; i<a[cur].size(); i++)
        {
        	int next = a[cur][i].first;
            int nextDist = dist + a[cur][i].second;
            if(nextDist < d[next])
            {
            	d[next] = nextDist;
                pq.push(make_pair(next, nextDist));
            }
        }
    }
}

int main(void)
{
	int M;
	cin >> N>>M;
	for(int i=1; i<= N; i++)
    	d[i] = INF;
    for(int i=0; i<M; i++)
    {
    	int s, e, d;
        cin >> s>>e>>d;
        a[s].push_back(make_pair(e,d));
    }
    dijkstra(1);
    return 0;
}