+C++ example
In C++, pairing std::priority_queue with std::greater<> builds a min-heap; lazy insertion together with the if (d > distance[from]) continue; guard implements the $O((V + E) \log V)$ priority-queue form directly.
#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();
// Discard stale priority-queue entries left over from earlier relaxations.
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() {
// Vertices are S(0), A(1), B(2), T(3), and U(4); no edge reaches 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;
}
Output:
0,3,1,4,INF