예제 : 최단경로

그래프의 간선들에 가중치가 없다면 DFS나 BFS를 이용해 최단거리를 구할 수 있다.

하지만 간선들에 가중치가 존재한다면 단순한 DFS나 BFS로 풀기에는 곤란해진다.

Dijkstra(다익스트라) 알고리즘은 가중치가 있는 그래프의 한 노드에서 다른 모든 노드로 가는 최소 Cost를 구하는 알고리즘이다.

동작 방식

다익스트라의 동작 방식을 gif로 보여주는 예시이다. (위의 동작은 개선된 다익스트라의 동작이다.)

인접 리스트 방식을 이용한 간선 저장

우선 간선에 대한 정보들을 인접 리스트로 저장해야 한다.

vector 선언

#include <vector>

using namespace std;

vector<pair<int, int> >	v[N];

이렇게 벡터를 구성하면 N개의 노드들에 대해 각각 간선의 정보를 저장할 수 있다.

만약 0번 노드에서 1번 노드 방향으로 가중치가 8인 간선이 존재한다면

v[0].push_back(1, 8);와 같은 방식으로 저장한다.

가중치가 추가되었을 뿐, 기존 BFS나 DFS와 인접 리스트를 만드는 방식은 크게 다르지 않다.

dist 배열 초기화

가중치가 없는 그래프를 탐색할 때에는 최단거리를 단순히 노드 수를 이용하여 구하였다면, 이제는 가중치의 합끼리 비교해야만 한다.

이를 위해 dist라는 배열을 따로 만들어 적당한 값으로 초기화 해주어야 하는데, dist는 그래프의 최단거리를 구하기 위해 메모이제이션을 사용하는데 필요한 배열이다.

#define INF 1000000000

int		dist[N];

void	init_dist()
{
	int		i;

	i = 0;
	while (i++ < N)
		dist[i] = INF;
}

dist 배열은 지속적으로 최솟값으로 갱신되어 나갈 것이기 때문에 충분히 큰 값으로 초기화가 필요하다.