길찾기3 다익스트라 길찾기

BFS 로 길찾기 가능하지만 간선 별로 가중치가 없을 때에 최적의 경로를 찾는 것이다. 간선 별 가중치에 따라 이동 시간이 늘어난다고 하였을 때에는 다익스트라 길찾기 쓴다.

목적지는 딱히 의미가 없고, 시작 노드로부터 각 노드까지의 최소 비용을 찾는 알고리즘이다.

 

각 노드 별로 탐색 시에 해당 경로까지의 비용을 갱신한다.

 

 

위의 3번 노드는 처음 35 비용이 저장되지만, 0 → 1 → 3 으로 탐색 되어질 때 25비용으로 갱신된다.

 

// BFS 로 길찾기 가능하지만 간선 별로 가중치가 없을 때에 최적의 경로를 찾는 것이다.
// 간선 별 가중치에 따라 이동 시간이 늘어난다고 하였을 때에는 다익스트라 길찾기 쓴다.
 
// 목적지는 딱히 의미가 없고, 

#include <iostream>
#include <queue>
#include <vector>
#include <list>
using namespace std;

struct Vertex
{
	// int data;
};

vector<Vertex> vertices;
vector<vector<int>> adjacent;; // 인접 행렬

void CreateGraph()
{
	vertices.resize(6);
	adjacent = vector<vector<int>>(6, vector<int>(6, -1));

	// 간선 연결 및 가중치 설정
	adjacent[0][1] = 15;
	adjacent[0][3] = 35;
	adjacent[1][0] = 15;
	adjacent[1][2] = 5;
	adjacent[1][3] = 10;
	adjacent[3][4] = 5;
	adjacent[5][4] = 5;
}

void Dijkstra(int here)
{
	// 구조체로 해도 되고 std::pair 로 해도 되고
	struct VertexCost
	{
		int vertex;
		int cost;
	};

	// BFS 에서는 queue 로 관리했다. 이유는 먼저 발견한 순서대로 탐색해야했기 때문이다.
	// 그러나 이제는 먼저 발견했다고 먼저 탐색하는 것이 아니기 때문에
	// list 혹은 다른 자료구조로 관리한다.
	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 를 이용해서 
		list<VertexCost>::iterator bestIt;
		int bestCost = INT32_MAX;

		for (auto it = discovered.begin(); it != discovered.end(); it++)
		{
			const int cost = it->cost;

			// 현재 찾는 코스트가 더 낮은 비용이면 bestCost 갱신
			if (bestCost > cost)
			{
				bestCost = cost;
				bestIt = it;
			}
		}

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

		// 방문. 더 짧은 경로를 이미 찾았다면 스킵
		if (best[here] < cost2)
			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;

			best[there] = nextCost;
			parent[there] = here;

			// {3,35} {3, 25} 가 2번 들어간다.
			discovered.push_back(VertexCost{ there, nextCost });
		}

	}
	
// 디버깅용 더미 데이터
	int a = 3;
}

int main()
{
	CreateGraph();
	Dijkstra(0);
}

 

디버깅 결과

시작 노드에서 각 노드까지의 최단 비용

 

시작 노드에 각 노드까지의 최단 비용일 때에 각 노드와 시작 노드 사이에 경로