최단 경로 알고리즘 - 1. 다익스트라 알고리즘 (Dijkstra Algorithm)

다익스트라 알고리즘(Dijkstra Algorithm)

최단 경로(shotest path)를 찾는 알고리즘으로,

시작 노드에서 다른 노드들 사이의 최단 경로를 찾는 알고리즘이다.

 

단, 음의 간선을 포함하면 안된다. (음수 사이클이 발생할 수 있기 때문)

 

다익스트라 알고리즘은 매번 '가장 비용이 적은 노드'를 선택하여 임의의 과정을 거치기 때문에

기본적으로 그리디 알고리즘으로 분류된다.

 

핵심 아이디어

방문하지 않은 노드 중, 최단 거리가 가장 짧은 노드를 선택. 그 노드를 기준으로 최단 거리 테이블을 갱신

 

알고리즘

1. 최단 거리 테이블 초기화 한다. (INF로 설정)
2. 시작 노드 설정한다. (시작 노드 비용은 0)
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
4. 해당 노드를 거쳐서 다른 노드로 가능 비용을 계산하여 최단 거리 테이블을 갱신한다.
5. 위 과정 중 3, 4 과정을 반복한다. (더이상 방문 가능한 노드가 없을 때 까지)

 

알고리즘 구현

BOJ 1753

 

1. 인접 행렬로 구현하는 경우 - 메모리 초과

#include <iostream>
#include <algorithm>

const int MAX_V = 20000;
const int INF = 1000000000; // 절대 나올 수 없는 경로값

int graph[MAX_V][MAX_V];
int dist[MAX_V];
bool visited[MAX_V];
int V, E, S;

using namespace std;

int getMinDistance()
{
	int minDist = INF;
	int idx = -1;
	
	for (int i = 0; i < V; i++)
	{
		if (visited[i] == false && dist[i] < minDist)
		{
			minDist = dist[i];
			idx = i;
		}
	}
	return idx;
}

void dijkstra(int start)
{
	for (int i = 0; i < V; i++)
	{
		dist[i] = graph[start][i];
	}

	dist[start] = 0;
	visited[start] = true;

	for (int i = 0; i < V - 1; i++) // 자신을 제외한 V - 1 개의 최단 경로 찾기
	{
		int u = getMinDistance();
		visited[u] = true;

		for (int v = 0; v < V; v++)
		{
			if (visited[v] == false && 
				dist[u] + graph[u][v] < dist[v])
			{
				dist[v] = dist[u] + graph[u][v];
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> V >> E >> S;

	S--;
	fill(graph[0], graph[0] + MAX_V * MAX_V, INF);
	fill(dist, dist + MAX_V, INF);

	for (int i = 0; i < V; i++)
	{
		graph[i][i] = 0;
	}

	for (int i = 0; i < E; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		graph[u - 1][v - 1] = w;
	}

	dijkstra(S);

	for (int i = 0; i < V; i++)
	{
		if (dist[i] != INF)
		{
			cout << dist[i] << '\n';
		}
		else
		{
			cout << "INF\n";
		}
	}

	return 0;
}

• 시간 복잡도 : O(V^2)
• 공간 복잡도 : O(V^2)

가장 짧은 거리를 찾을 때 순차 탐색을 하므로 V(정점의 개수) 크기가 클수록 속도가 느려진다는 단점이 있다.

 

2. 인접 리스트와 힙(=우선순위 큐)을 사용하는 경우 - 성공

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

using namespace std;

const int MAX_V = 20000;
const int INF = 1000000000; // 절대 나올 수 없는 경로값

struct Edge
{
	int v, d;

	bool operator > (const Edge& rhs) const
	{
		return d > rhs.d;
	}
};

vector<Edge> graph[MAX_V]; // 인접 리스트
bool visited[MAX_V];
int dist[MAX_V];
int V, E, S;

void dijkstra(int start)
{
	dist[start] = 0;

	priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
	pq.push({ start, 0 });

	while (!pq.empty())
	{
		int u = pq.top().v; // 현재 노드
		int d = pq.top().d; // 현재 노드까지 거리(비용)
		pq.pop();

		if (dist[u] < d)
		{
			continue;
		}

		for (int i = 0; i < graph[u].size(); i++)
		{
			int v = graph[u][i].v;
			int alt = d + graph[u][i].d; // 대체 경로 길이

			if (alt < dist[v])
			{
				dist[v] = alt;
				pq.push({ v, alt });
			}
		}
	}

}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> V >> E >> S;

	S--;

	fill(dist, dist + MAX_V, INF);

	for (int i = 0; i < E; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		graph[u - 1].push_back({ v - 1, w });
	}

	dijkstra(S);

	for (int i = 0; i < V; i++)
	{
		if (dist[i] != INF)
		{
			cout << dist[i] << '\n';
		}
		else
		{
			cout << "INF\n";
		}
	}

	return 0;
}

• 시간 복잡도 : O(ElogV)
  • 우선순위 큐에서 꺼낸 현재 노드에 연결된 간선 모두 확인 - 간선의 개수(E) 만큼 확인
  • 우선순위 큐에 간선을 넣고 빼는 과정 - logE
  • 따라선 모든 간선을 우선순위 큐에 넣고 뺀다고 했을 때 O(ElogE) 의 시간 복잡도를 갖는다.
  • 이때, 중복 간선을 포함하지 않는 경우, E는 항상 V^2 이하이다. (모든 노드가 연결 되어 있는 경우 V * (V-1))
  • logE < log(V^2)이다. log(V^2)은 2logV이기 때문에 O(logV)로 표현할 수 있다.
  • 따라서, 다익스트라 알고리즘 전체 시간 복잡도를 O(ElogV) 로 표현할 수 있다. (ElogE)

 

References

음수 간선이 존재하면 안되는 이유

[알고리즘] 다익스트라(Dijkstra) 알고리즘