다익스트라(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;
‌}
}