[자료구조] 데이크스트라 알고리즘

최단 경로 문제를 푸는 알고리즘 중에 하나인 데이크스트라의 알고리즘은 에드거 데이크스트라가 만들었다. 데이크스트라 알고리즘 규칙은 다음과 같다.

1. 시작 정점을 현재 정점으로 한다.
2. 현재 정점에 인접한 모든 정점을 확인해서 시작 정점으로부터 알려진 모든 위치까지의 가중치를 계산하고 기록한다.
3. 다음 현재 정점을 결정하려면 시작 정점으로부터 도달할 수 있는 방문하지 않은 가장 저렴한 알려진 정점을 찾는다.
4. 그래프 내 모든 정점을 방문할 때까지 1~3단계를 반복한다.

애틀랜타부터 다른 도시까지의 가장 저렴한 경로를 찾아보자. 시작 정점은 아틀랜타가 된다. 다음으로 인접한 정점을 모두 확인해서 가중치를 기록한다.

Atlanta	Boston	Chicago	Denver	El Paso
	$100	?	$160	?

현재로서는 애틀랜타로부터 출발해서 보스턴으로 가는 것이 덴버로 가는 것보다 저렴하기 때문에 보스턴을 현재 정점으로 한다.

보스턴에서 출발하는 두 경로를 확인한 후에 시작 정점인 애틀랜타로부터 알려진 모든 위치로 가는 경로의 비용을 새롭게 계산해서 기록한다. 

Atlanta	Boston	Chicago	Denver	El Paso
	$100	$220	$160	?

보스턴에서 덴버로 가는 경로도 있지만 기존의 비용보다 높기 때문에 표에는 업데이트하지 않는다. 현재 정점(보스턴)에서 갈 수 있는 모든 경로를 알아봤으므로 이제 시작 정점이었던 애틀랜타로부터 갈 수 있는 도시 중에 가장 저렴한 경로를 현재 정점으로 한다. 덴버를 현재 정점으로 한다.

이제 덴버를 떠나는 경로를 검사한다. 한 경로는 시카고로 가는 40달러 비행이며 애틀랜타에서 시카고로 가는 더 저렴한 경로를 찾았으므로 표에 업데이트할 수 있다. 새롭게 등장한 엘 페소의 비용도 업데이트를 한다.

Atlanta	Boston	Chicago	Denver	El Paso
	$100	$200	$160	$300

이제 방문하지 않은 정점은 두 개 남았다. 시카고와 엘페 소다. 

애틀랜타에서 시카고로 가는 알려진 가장 저렴한 경로는 애틀랜타에서 엘 페소로 가는 것보다 저렴하기 때문에 현재 정점은 시카고가 된다. 시카고에서 떠나는 비행기는 엘 페소로 가는 80달러 비행기며 기존 경로보다 저렴하므로 업데이트를 한다.

Atlanta	Boston	Chicago	Denver	El Paso
	$100	$200	$160	$280

마지막으로 엘 페소를 현재 정점으로 하며 경로는 보스턴으로 떠나는 100달러짜리 비행이 유일하다.

이 데이터가 있어도 애틀랜타에서 다른 도시로 가는 더 저렴한 경로가 없기 때문에 표는 업데이트되지 않는다. 모든 작업이 끝나면 애틀랜타로부터 가장 저렴한 가격을 모두 알 수 있다.

Atlanta	Boston	Chicago	Denver	El Paso
	$100	$200	$160	$280

---

코드 구현

가장 저렴한 비행 요금을 구하는 코드다. 경로까지 추가하려면 여러 작업을 더해야 할 것 같다. 이미 방문한 데이터를 한꺼번에 업데이트하는 것 때문에 고생했는데 이렇게 구현하는 것이 맞는지는 모르겠다. 결과는 동일하게 나온다.

#include <string>
#include <vector>
#include <list>
#include <map>
#include <iostream>
using namespace std;

class CCity
{
public:
	CCity(string _name) : name(_name) {}

	void add_route(CCity* city, int _price)
	{
		routes.insert(pair<CCity*, int>(city, _price));
	}
	string name;
	map<CCity*, int> routes;
};

void update_price(CCity* start, map<CCity*, int>& route_price_datas, list<CCity*>& visited_cites)
{
	// 현재 경로까지의 금액을 가져온다.
	auto it_curr_info = route_price_datas.find(start);

	// 현재 도시로부터 각 경로를 확인한다.
	for (auto it_route = start->routes.begin(); it_route != start->routes.end(); it_route++)
	{
		// 경로상에 있는 도시 검색, 검색하려는 도시가 아니라면 패스
		auto it_route_info = route_price_datas.find(it_route->first);
		if (it_route_info == route_price_datas.end())
			continue;

		// 기존 경로보다 저렴하다면 데이터 갱신
		if (it_route_info->second > it_curr_info->second + it_route->second)
		{
			it_route_info->second = it_curr_info->second + it_route->second;

			auto it = find(visited_cites.begin(), visited_cites.end(), it_route->first);
			if (it != visited_cites.end())
				update_price(*it, route_price_datas, visited_cites);
		}
	}
}

void dijkstra(CCity* start, vector<CCity*> others)
{
	map<CCity*, int> route_price_datas;
	list<CCity*> visited_cites;
	CCity* pCurrent = start;

	// 시작 도시는 언제나 0이다.
	route_price_datas.insert(pair<CCity*, int>(pCurrent, 0));

	// 초기 금액은 최대로 설정한다. (원하는 경로만 확인한다.)
	for (int i = 0; i < (int)others.size(); i++)
		route_price_datas.insert(pair<CCity*, int>(others[i], numeric_limits<int>::max()));

	while (pCurrent != nullptr)
	{
		// 현재 정점을 방문 경로에 추가.
		visited_cites.push_back(pCurrent);
		update_price(pCurrent, route_price_datas, visited_cites);
		
		// 다음 방문할 도시를 정한다.
		CCity* pNext = nullptr;
		long min_price = numeric_limits<int>::max();

		// 하위 정점 검색
		for (auto it_route = pCurrent->routes.begin(); it_route != pCurrent->routes.end(); ++it_route)
		{
			auto it = find(visited_cites.begin(), visited_cites.end(), it_route->first);
			// 가장 저렴하고 방문하지 않은 도시로 이동한다.
			if (it_route->second < min_price && it == visited_cites.end())
			{
				min_price = it_route->second;
				pNext     = it_route->first;
			}
		}

		// 최초 정점부터 다시 검색
		if (pNext == nullptr)
		{
			for (auto it_route = start->routes.begin(); it_route != start->routes.end(); ++it_route)
			{
				auto it = find(visited_cites.begin(), visited_cites.end(), it_route->first);
				// 가장 저렴하고 방문하지 않은 도시로 이동한다.
				if (it_route->second < min_price && it == visited_cites.end())
				{
					min_price = it_route->second;
					pNext = it_route->first;
				}
			}
		}

		pCurrent = pNext;
	}

	auto itt = route_price_datas.begin();
	for (; itt != route_price_datas.end(); ++itt)
	{
		cout << start->name << "->" << itt->first->name << " : $" << itt->second << endl;
	}
}

int main()
{
	CCity* atlanta = new CCity("Atlanta");
	CCity* boston = new CCity("Boston");
	CCity* chicago = new CCity("Chicago");
	CCity* denver = new CCity("Denver");
	CCity* elpaso = new CCity("El Paso");
	
	atlanta->add_route(boston, 100);
	atlanta->add_route(denver, 160);
	boston->add_route(chicago, 120);
	boston->add_route(denver, 180);
	chicago->add_route(elpaso, 80);
	denver->add_route(chicago, 40);
	denver->add_route(elpaso, 140);
	elpaso->add_route(boston, 100);

	vector<CCity*> cities = { boston, chicago, denver, elpaso };
	dijkstra(atlanta, cities);

	return 0;
}