CS/알고리즘

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

nowkoes 2023. 6. 17. 00:00

<본 카테고리는 "코딩 테스트를 위한 자료 구조와 알고리즘 with C++을 기반으로 작성하였습니다>

다익스트라 알고리즘

개요

　그래프에서 단일 시작 최단 경로 문제는 시작 정점과 목적 정점이 주어졌을 때, 시작 정점에서 목적 정점까지 이어지는 최소 비용 경로를 찾는 문제다. 이 문제를 해결하는 여러 알고리즘 중 하나가 다익스트라 알고리즘(Dijkstra's algorithm)이다.

　다익스트라 알고리즘은 음수 가중치를 갖지 않는 그래프에서 사용되는 최단 경로 탐색 알고리즘이다. 이 알고리즘은 프림의 최소 신장 트리(MST) 알고리즘을 변형한 것으로, 다음과 같은 절차를 따른다.

 

  1. 시작 노드를 설정
  2. 시작 노드의 거리 값은 0으로, 이를 제외한 모든 노드의 거리 값은 무한대로 초기화
  3. 모든 거리 값을 최소 힙에 추가
  4. 최소 힙으로부터 꺼낸 정점 U와 인접한 모든 정점 V에 대해, 만약 V의 거리 값이 (U의 거리 값 + (U,V) 에지 가중치) 보다 크다면, V의 거리 값을 (U의 거리 값 + (U,V) 에지 가중치)으로 설정
  5. 만약 목적 정점이라면 알고리즘은 종료, 아니면 다시 반복

예시

 

　다음과 같은 그래프가 있고, 시작 정점 1에서 목적 정점 6까지 최단 경로를 탐색해 보자.

 

 

　정점 1과 인접한 정점인 정점 2와 정점 5중 어느 경로로 갈지 선택해 보자.

 

  • 정점 1과 정점 2의 거리 값은 0 + 2 = 2
  • 정점 1과 정점 5의 거리 값은 0 + 3 = 3

 

　따라서 정점 2로 이동한다.

 

 

　정점 2와 인접한 정점인 정점 1, 정점 5, 정점 4를 비교해 보자.

 

  • 정점 1: 이미 방문함
  • 정점 2와 정점 5의 거리 값: 2 + 5 = 7, 하지만 이미 3인 최솟값이 있으므로 갱신하지 않음
  • 정점 2와 정점 4의 거리 값: 2 + 1 = 3

 

　정점 5의 거리 값도 3이고, 정점 4의 거리 값도 3이므로 둘 중 어느 것을 먼저 가도 상관없다. 필자는 5부터 가도록 하겠다.

 

 

　정점 5와 인접한 정점인 정점 1, 정점 2, 정점 4, 정점 8을 비교해 보자.

　

  • 정점 1, 2: 이미 방문함
  • 정점 5와 정점 4의 거리 값: 3 + 3 = 6, 하지만 이미 3인 최솟값이 있으므로 갱신하지 않음
  • 정점 5와 정점 8의 거리 값: 3 + 3 = 6

 

　따라서 최솟값을 갖는 정점 4로 이동한다.

 

 

　정점 4와 인접한 정점 5, 정점 2, 정점 6, 정점 3, 정점 8을 비교해 보자.

 

  • 정점 2, 5, 8: 이미 방문함
  • 정점 4와 정점 6의 거리 값: 3 + 4 = 7
  • 정점 4와 정점 3의 거리 값: 3 + 2 = 5

 

　따라서 정점 3으로 이동한다

 

 

　여기서 조금 헷갈리는데, 다익스트라 알고리즘은 현재 고려 중인 노드에서 이동할 수 있는 노드들 중 '아직 방문하지 않은 노드들 중 최소 거리를 가진 노드'를 선택하게 된다. 여기서 정점 3에 도착했을 때 인접한 정점은 4와 7이다. 이 두 정점 중 아직 방문하지 않은 정점은 7 뿐이므로, 정점 7의 거리가 업데이트된다.

 

　그런데 다음 정점을 선택할 때 그래프 전체에서 아직 방문하지 않은 정점 중 최단 거리를 가진 정점을 선택해야 하므로, 정점 8로 이동해야 한다.

 

 

　마지막으로 정점 6을 방문하고 최단 경로를 계산한다. 정점 6이라는 목적 지점을 찾았으므로 시작 지점 정점 1까지 백트래킹을 통해 최단 경로를 찾을 수 있다.

 

  • 1 → 2 → 4 → 6

구현

#include <string>
#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <limits>
#include <algorithm>
using us = unsigned;

template <typename T>
struct edge
{
	us _src, _dst;
	T _weight;
};

template <class T>
class graph
{
	us _v;
	std::vector<edge<T>> _edges;

public:
	graph(us n) : _v(n)
	{

	}

	auto vertices() const
	{
		return _v;
	}

	auto& edges() const
	{
		return _edges;
	}

	auto edges(us v) const
	{
		std::vector<edge<T>> edges_from_v;

		for (const auto& e : _edges)
		{
			if (e._src == v)
				edges_from_v.push_back(e);
		}

		return edges_from_v;
	}

	void add_edge(edge<T>&& e)
	{
		if (e._src >= 1 && e._src <= _v && e._dst >= 1 && e._src <= _v)
			_edges.push_back(e);

		else
			std::cerr << "error: invalid range\n";
	}

	template <typename t>
	friend std::ostream& operator << (std::ostream& os, const graph<t>& g)
	{
		for (us i = 1; i < g.vertices(); ++i)
		{
			os << i << ":\t";

			auto edges = g.edges(i);

			for (const auto& e : edges)
				os << "{" << e._dst << ": " << e._weight << "}, ";
			os << "\n";
		}

		return os;
	}
};


template <typename T>
struct label
{
	us _ID;
	T _distance;

	inline bool operator > (const label<T>& l) const
	{
		return this->_distance > l._distance;
	}
};

　다익스트라 알고리즘 구현에 필요한 에지, 그래프, 라벨을 구현하였다.

 

template <typename T>
auto dijkstra(const graph<T>& g, us src, us dst)
{
	std::priority_queue<label<T>, std::vector<label<T>>, std::greater<label<T>>> pq;
	std::vector<T> distance(g.vertices(), std::numeric_limits<T>::max());
	std::set<us> visited;
	std::vector<us> parent(g.vertices());

	pq.push(label<T>{src, 0});
	parent[src] = src;

　다익스트라 알고리즘을 구현한 함수다. 먼저 최소 힙 pq, 거리 값 distacne, 방문한 정점 visited, 이동 경로를 기억할 벡터 parent를 초기화한다. 그리고 시작 정점을 최소 힙과 이동 경로에 추가한다.

 

	while (!pq.empty())
	{
		auto current = pq.top();
		pq.pop();

		if (current._ID == dst)
		{
			std::cout << current._ID << "번 정점에 도착\n";
			break;
		}

　현재 정점을 꺼내서 목적지에 도착했는지 확인한다.

 

		if (visited.find(current._ID) == visited.end())
		{
			std::cout << current._ID << "번 정점에 안착\n";

			for (const auto& e : g.edges(current._ID))
			{
				auto n = e._dst;
				auto new_distnce = current._distance + e._weight;

				if (new_distnce < distance[n])
				{
					pq.push(label<T>{n, new_distnce});
					parent[n] = current._ID;
					distance[n] = new_distnce;
				}
			}

			visited.insert(current._ID);
		}
	}

　현재 정점을 이전에 방문하지 않았다면, 현재 정점과 연결된 모든 에지에 대해 인접한 정점의 거리 값이 새로운 경로에 의한 거리 값보다 크면 힙에 추가하고, 거리 값을 업데이트한다.

 

	std::vector<us> mst;
	auto current = dst;

	while (current != src)
	{
		mst.push_back(current);
		current = parent[current];
	}

	mst.push_back(src);
	std::reverse(mst.begin(), mst.end());

	return mst;
}

　노드들의 방문을 마쳤으니, 최단 경로를 계산해 보자. 이는 백트래킹 방식으로 목적 정점부터 시작 정점까지 거리의 최솟값을 벡터에 추가하면 된다.

 

int main()
{
	graph<us> g(9);

	std::map<us, std::vector<std::pair<us, us>>> edge_map;
	edge_map[1] = { {2, 2}, {5, 3} };
	edge_map[2] = { {1, 2}, {5, 5}, {4, 1} };
	edge_map[3] = { {4, 2}, {7, 3} };
	edge_map[4] = { {2, 1}, {3, 2}, {5, 2}, {6, 4}, {8, 5} };
	edge_map[5] = { {1, 3}, {2, 5}, {4, 2}, {8, 3} };
	edge_map[6] = { {4, 4}, {7, 4}, {8, 1} };
	edge_map[7] = { {3, 3}, {6, 4} };
	edge_map[8] = { {4, 5}, {5, 3}, {6, 1} };

	for (const auto& i : edge_map)
	{
		for (const auto& j : i.second)
			g.add_edge(edge<us>{i.first, j.first, j.second});
	}

	std::cout << "[Input]\n";
	std::cout << g << "\n";

	auto mst = dijkstra(g, 1, 6);
	std::cout << "\n[1번과 6번 사이의 최단 경로]\n";
	
	for (const auto& val : mst)
		std::cout << val << "\n";
	std::cout << "\n";
}

출력

 

총합본

더보기 
#include <string>
#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <limits>
#include <algorithm>
using us = unsigned;

template <typename T>
struct edge
{
	us _src, _dst;
	T _weight;
};

template <class T>
class graph
{
	us _v;
	std::vector<edge<T>> _edges;

public:
	graph(us n) : _v(n)
	{

	}

	auto vertices() const
	{
		return _v;
	}

	auto& edges() const
	{
		return _edges;
	}

	auto edges(us v) const
	{
		std::vector<edge<T>> edges_from_v;

		for (const auto& e : _edges)
		{
			if (e._src == v)
				edges_from_v.push_back(e);
		}

		return edges_from_v;
	}

	void add_edge(edge<T>&& e)
	{
		if (e._src >= 1 && e._src <= _v && e._dst >= 1 && e._src <= _v)
			_edges.push_back(e);

		else
			std::cerr << "error: invalid range\n";
	}

	template <typename t>
	friend std::ostream& operator << (std::ostream& os, const graph<t>& g)
	{
		for (us i = 1; i < g.vertices(); ++i)
		{
			os << i << ":\t";

			auto edges = g.edges(i);

			for (const auto& e : edges)
				os << "{" << e._dst << ": " << e._weight << "}, ";
			os << "\n";
		}

		return os;
	}
};


template <typename T>
struct label
{
	us _ID;
	T _distance;

	inline bool operator > (const label<T>& l) const
	{
		return this->_distance > l._distance;
	}
};

template <typename T>
auto dijkstra(const graph<T>& g, us src, us dst)
{
	std::priority_queue<label<T>, std::vector<label<T>>, std::greater<label<T>>> pq;
	std::vector<T> distance(g.vertices(), std::numeric_limits<T>::max());
	std::set<us> visited;
	std::vector<us> parent(g.vertices());

	pq.push(label<T>{src, 0});
	parent[src] = src;

	while (!pq.empty())
	{
		auto current = pq.top();
		pq.pop();

		if (current._ID == dst)
		{
			std::cout << current._ID << "번 정점에 도착\n";
			break;
		}

		if (visited.find(current._ID) == visited.end())
		{
			std::cout << current._ID << "번 정점에 안착\n";

			for (const auto& e : g.edges(current._ID))
			{
				auto n = e._dst;
				auto new_distnce = current._distance + e._weight;

				if (new_distnce < distance[n])
				{
					pq.push(label<T>{n, new_distnce});
					parent[n] = current._ID;
					distance[n] = new_distnce;
				}
			}

			visited.insert(current._ID);
		}
	}

	std::vector<us> mst;
	auto current = dst;

	while (current != src)
	{
		mst.push_back(current);
		current = parent[current];
	}

	mst.push_back(src);
	std::reverse(mst.begin(), mst.end());

	return mst;
}

int main()
{
	graph<us> g(9);

	std::map<us, std::vector<std::pair<us, us>>> edge_map;
	edge_map[1] = { {2, 2}, {5, 3} };
	edge_map[2] = { {1, 2}, {5, 5}, {4, 1} };
	edge_map[3] = { {4, 2}, {7, 3} };
	edge_map[4] = { {2, 1}, {3, 2}, {5, 2}, {6, 4}, {8, 5} };
	edge_map[5] = { {1, 3}, {2, 5}, {4, 2}, {8, 3} };
	edge_map[6] = { {4, 4}, {7, 4}, {8, 1} };
	edge_map[7] = { {3, 3}, {6, 4} };
	edge_map[8] = { {4, 5}, {5, 3}, {6, 1} };

	for (const auto& i : edge_map)
	{
		for (const auto& j : i.second)
			g.add_edge(edge<us>{i.first, j.first, j.second});
	}

	std::cout << "[Input]\n";
	std::cout << g << "\n";

	auto mst = dijkstra(g, 1, 6);
	std::cout << "\n[1번과 6번 사이의 최단 경로]\n";
	
	for (const auto& val : mst)
		std::cout << val << "\n";
	std::cout << "\n";
}

요약

다익스트라 알고리즘
1. 정의: 가중치가 양수인 그래프에서 최단 경로를 계산하는 알고리즘
2. 과정
　a. 시작 정점 거리 0으로 초기화
　b. 시작 정점 제외 모든 정점 거리 무한으로 초기화
　c. 정점을 하나씩 추가하며 목적지에 도착할 때까지 거리값을 최솟값으로 갱신
　d. 목적지에서 백트래킹 방식으로 시작지점까지 최단 거리 출력
3. 시간 복잡도
　- O(E + VlogV) 혹은 O(ElogV)
반응형
저작자표시 비영리 변경금지

'CS > 알고리즘' 카테고리의 다른 글

[알고리즘] 벨만-포드 알고리즘  (0) 2023.06.23
[알고리즘] 프림 알고리즘  (0) 2023.06.15
[알고리즘] 그래프 순회 문제  (0) 2023.06.14
[알고리즘] 그리디 알고리즘 - 그래프 컬러링  (0) 2023.05.30
[알고리즘] 그리디 알고리즘 - 최소 신장 트리 문제 (2)  (0) 2023.05.29

'CS/알고리즘'의 다른글

  • 현재글[알고리즘] 다익스트라 최단 경로 알고리즘

관련글

댓글

티스토리툴바