Dijkstra

Dijkstra(다익스트라)

• 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다.

• 양의 가중치를 갖는 간선을 사용하는 그래프에서 사용된다.

• 각 정점들은 시작정점에서 부터의 거리를 갖는 distance를 가지게 된다.

• distance는 탐색도중 시작정점으로부터 해당 정점까지의 거리 중 더 짧은 거리를 찾을 때 마다 갱신된다.

void Dijkstra(int here)
{
	struct VertexCost
	{
		int vertex;
		int cost;
	};

	list<VertexCost> discovered; // 발견 목록
	vector<int> best(vertices.size(), INT32_MAX); // 각 정점별로 지금까지 발견한 최소 거리
	vector<int> parent(6, -1);

	discovered.push_back(VertexCost{ here, 0 });
	best[here] = 0;
	parent[here] = here;

	while (discovered.empty() == false)
	{

		list<VertexCost>::iterator bestIt;
		int bestCost = INT32_MAX;
        	// 현재 까지 발견한 루트들 중 제일 좋은 후보를 찾는다.
		for (auto it = discovered.begin() ; it != discovered.end() ; it++)
		{

			if (bestCost > it->cost)
			{
				bestCost = it->cost;
				bestIt = it;
			}
		}

		int cost = bestIt->cost;
		here = bestIt->vertex;
		discovered.erase(bestIt);

		// 더 짧은 경로를 이미 찾았다면 스킵
		if (best[here] < cost)
			continue;

		// 방문
		for (int there = 0; there < 6;there++)
		{
			if (adjacent[here][there] == -1)
				continue;

			// 다음 경로 까지 더 좋은 경로가 이미 있다면 스킵.
			int nextCost = best[here] + adjacent[here][there];
			if (nextCost >= best[there])
				continue;
                
			// 여기까지 온 경로는
			// here까지 오는 최단 경로 + there까지 가는 최단 경로 이므로 추가해준다.
			// 하지만 최단 경로가 다음 반복에 찾아질 수도 있다.
			best[there] = nextCost;
			parent[there] = here;
			discovered.push_back(VertexCost{ there,nextCost });
		}

	}
}