+C++20
C++20판은 정수 비용을 long long에 담는다. 정점 번호와 출발점은 유효한 인덱스이고, 모든 가중치는 0 이상이며 계산하는 경로 합은 long long의 최댓값보다 작다고 전제한다. 그 최댓값 INF는 도달 불가 표시에만 쓰고, 출력에서는 TypeScript와 같이 Infinity로 표시한다.
#include <cstddef>
#include <iostream>
#include <limits>
#include <vector>
using Distance = long long;
struct Edge { std::size_t to; Distance weight; };
using Graph = std::vector<std::vector<Edge>>;
constexpr Distance INF = std::numeric_limits<Distance>::max();
std::vector<Distance> dijkstra(const Graph& graph, std::size_t start) {
const auto n = graph.size();
std::vector<Distance> distance(n, INF);
std::vector<bool> settled(n, false);
distance[start] = 0;
for (std::size_t step = 0; step < n; ++step) {
auto from = n;
for (std::size_t vertex = 0; vertex < n; ++vertex) {
if (!settled[vertex] && (from == n || distance[vertex] < distance[from])) {
from = vertex;
}
}
// 도달할 수 있는 미확정 정점이 더 없으면 종료한다.
if (from == n || distance[from] == INF) break;
settled[from] = true;
for (const auto& edge : graph[from]) {
if (settled[edge.to]) continue;
const auto candidate = distance[from] + edge.weight;
if (candidate < distance[edge.to]) distance[edge.to] = candidate;
}
}
return distance;
}
int main() {
// 정점 순서는 S, A, B, T, U이다.
const Graph graph{{{1, 4}, {2, 1}}, {{3, 1}}, {{1, 2}, {3, 5}}, {}, {}};
const auto distance = dijkstra(graph, 0);
for (std::size_t i = 0; i < distance.size(); ++i) {
if (i != 0) std::cout << ',';
if (distance[i] == INF) std::cout << "Infinity";
else std::cout << distance[i];
}
std::cout << '\n';
return 0;
}
0,3,1,4,Infinity
TypeScript