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

안 가본 노드 중에 가장 빨리 갈 수 있는 노드에 가서 거리 기록하는 일을 반복

#include <iostream>
#include <limits>
#include <queue>
#include <vector>

constexpr int VERTEX_COUNT = 5;
constexpr int distances[5][5] = {
	{ 0,-1, 6, 6,-1},
	{ 3, 0,-1,-1,-1},
	{-1,-1, 0, 2,-1},
	{-1, 1, 1, 0,-1},
	{-1, 4,-1, 2, 0},
};
/*
constexpr int VERTEX_COUNT = 6;
constexpr int distances[VERTEX_COUNT][VERTEX_COUNT] = {
	{ 0, 2, 5, 1,-1,-1},
	{ 2, 0, 3, 2,-1,-1},
	{ 5, 3, 0, 3, 1, 5},
	{ 1, 2, 3, 0, 1,-1},
	{-1,-1, 1, 1, 0, 2},
	{-1,-1, 5,-1, 2, 0},
};
*/
struct Vertex
{
	const int id;
	const int index;
	int parent;
	int distance;
	bool visit;
	Vertex(int id)
		: id(id)
		, index(id - 1)
		, parent(-1)
		, distance(std::numeric_limits<int>::max())
		, visit(false)
	{
	}
};

auto greater = [](const auto lhs, const auto rhs)
{
	return lhs->distance > rhs->distance;
};

std::priority_queue<std::shared_ptr<Vertex>, std::vector<std::shared_ptr<Vertex>>, decltype(greater)> sorted_queue;
std::vector<std::shared_ptr<Vertex>> vertices;

int main()
{
	for (int i = 0; i < VERTEX_COUNT; i++)
	{
		std::shared_ptr<Vertex> vertex = std::make_shared<Vertex>(i + 1);
		vertices.push_back(vertex);
	}

	int index = 3;
	auto start = vertices[index];
	start->distance = 0;

	sorted_queue.push(start);

	while (false == sorted_queue.empty())
	{
		auto current = sorted_queue.top();
		current->visit = true;
		sorted_queue.pop();
		
		for (int i = 0; i < VERTEX_COUNT; i++)
		{
			int distance = distances[current->index][i];
			std::shared_ptr<Vertex> adjacent = vertices[i];
			if (0 > distance || current->index == i || true == adjacent->visit)
			{
				continue;
			}

			if (adjacent->distance > current->distance + distance)
			{
				adjacent->distance = current->distance + distance;
				adjacent->parent = current->id;
				sorted_queue.push(adjacent);
			}
		}
	}

	for (auto vertex : vertices)
	{
		std::cout << "id:" << vertex->id << ", parent:" << vertex->parent << ", distance:" << vertex->distance << std::endl;
	}
}