+C++ 예제
C++에서는 std::priority_queue에 std::greater<>를 넘겨 최소 힙을 구성하고, 위에서 설명한 지연 삽입(lazy insertion)과 if (d > distance[from]) continue; 가드로 $O((V + E) \log V)$ 다익스트라를 구현한다.
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
struct Edge {
int to;
std::int64_t weight;
};
constexpr std::int64_t kInf = std::numeric_limits<std::int64_t>::max();
std::vector<std::int64_t> dijkstra(
const std::vector<std::vector<Edge>>& graph, int start) {
std::vector<std::int64_t> distance(graph.size(), kInf);
using Entry = std::pair<std::int64_t, int>;
std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> pq;
distance[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
auto [d, from] = pq.top();
pq.pop();
// 지연 삽입(lazy insertion)으로 남은 낡은 항목은 건너뛴다.
if (d > distance[from]) continue;
for (const Edge& edge : graph[from]) {
std::int64_t candidate = d + edge.weight;
if (candidate < distance[edge.to]) {
distance[edge.to] = candidate;
pq.push({candidate, edge.to});
}
}
}
return distance;
}
int main() {
// 정점 순서는 S(0), A(1), B(2), T(3), U(4)이며 U로 들어오는 간선은 없다.
const std::vector<std::vector<Edge>> graph{
{{1, 4}, {2, 1}}, {{3, 1}}, {{1, 2}, {3, 5}}, {}, {}};
const auto dist = dijkstra(graph, 0);
for (std::size_t i = 0; i < dist.size(); ++i) {
if (i > 0) std::cout << ',';
if (dist[i] == kInf) std::cout << "INF";
else std::cout << dist[i];
}
std::cout << '\n';
return 0;
}
실행 결과:
0,3,1,4,INF