int[] dijkstra(List<List<Edge>> graph, int source) {
int[] dist = new int[graph.size()];
Arrays.fill(dist, INF);
PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
dist[source] = 0;
heap.add(new int[] {source, 0});
while (!heap.isEmpty()) {
int[] state = heap.remove();
if (state[1] != dist[state[0]]) continue;
for (Edge edge : graph.get(state[0])) if (state[1] + edge.weight < dist[edge.to]) {
dist[edge.to] = state[1] + edge.weight;
heap.add(new int[] {edge.to, dist[edge.to]});
}
}
return dist;
}
def dijkstra(graph, source: int) -> list[int]:
dist = [INF] * len(graph)
dist[source] = 0
heap = [(0, source)]
while heap:
cost, node = heappop(heap)
if cost != dist[node]:
continue
for nxt, weight in graph[node]:
if cost + weight < dist[nxt]:
dist[nxt] = cost + weight
heappush(heap, (dist[nxt], nxt))
return dist
def dijkstra(graph: Vector[Vector[Edge]], source: Int): Array[Int] =
val dist = Array.fill(graph.length)(INF)
val heap = scala.collection.mutable.PriorityQueue[(Int, Int)]()(Ordering.by(-_._1))
dist(source) = 0
heap.enqueue((0, source))
while heap.nonEmpty do
val (cost, node) = heap.dequeue()
if cost == dist(node) then
for edge <- graph(node) do
if cost + edge.weight < dist(edge.to) then
dist(edge.to) = cost + edge.weight
heap.enqueue((dist(edge.to), edge.to))
dist
std::vector<int> dijkstra(const std::vector<std::vector<Edge>>& graph, int source) {
std::vector<int> dist(graph.size(), INF);
std::priority_queue<State, std::vector<State>, std::greater<State>> heap;
dist[source] = 0;
heap.push({0, source});
while (!heap.empty()) {
auto [cost, node] = heap.top();
heap.pop();
if (cost != dist[node]) continue;
for (const Edge& edge : graph[node]) if (cost + edge.weight < dist[edge.to]) {
dist[edge.to] = cost + edge.weight;
heap.push({dist[edge.to], edge.to});
}
}
return dist;
}