Thuật toán Dijkstra

// Dijkstra's algorithm: shortest distances from one source in a graph whose edge weights are all >= 0.
// A priority queue always hands us the closest vertex we have not finished yet — and with no
// negative edges, nothing found later can beat that distance, so it is final.

/** @typedef {[to: number, weight: number]} Edge an edge to `to`, with weight >= 0 */

/**
 * The priority queue: a binary min-heap of [distance, vertex] pairs, stored in an array where
 * the children of index i live at 2i + 1 and 2i + 2. Ties on distance go to the smaller vertex,
 * so the result never depends on the order entries happened to arrive in.
 */
class MinHeap {
  /** @type {Array<[number, number]>} */
  #items = [];

  get size() {
    return this.#items.length;
  }

  /** @param {[number, number]} item */
  push(item) {
    this.#items.push(item);
    this.#siftUp(this.#items.length - 1);
  }

  /** Removes and returns the smallest pair. Call only when size > 0. */
  pop() {
    const items = this.#items;
    const top = items[0];
    const last = items.pop();
    if (items.length > 0) {
      items[0] = last; // move the last leaf to the root, then let it sink to its place
      this.#siftDown(0);
    }
    return top;
  }

  /** @param {number} child */
  #siftUp(child) {
    while (child > 0) {
      const parent = (child - 1) >> 1;
      if (!isLess(this.#items[child], this.#items[parent])) return;
      this.#swap(child, parent);
      child = parent;
    }
  }

  /** @param {number} parent */
  #siftDown(parent) {
    while (true) {
      const smallest = this.#smallestOf(parent);
      if (smallest === parent) return;
      this.#swap(parent, smallest);
      parent = smallest;
    }
  }

  /**
   * The index of the smallest pair among `index` and its (up to two) children.
   * @param {number} index
   */
  #smallestOf(index) {
    let smallest = index;
    for (const child of [2 * index + 1, 2 * index + 2]) {
      if (child < this.#items.length && isLess(this.#items[child], this.#items[smallest])) smallest = child;
    }
    return smallest;
  }

  /**
   * @param {number} a
   * @param {number} b
   */
  #swap(a, b) {
    [this.#items[a], this.#items[b]] = [this.#items[b], this.#items[a]];
  }
}

/**
 * Orders [distance, vertex] pairs by distance, then by vertex.
 * @param {[number, number]} a
 * @param {[number, number]} b
 */
function isLess(a, b) {
  if (a[0] !== b[0]) return a[0] < b[0];
  return a[1] < b[1];
}

/**
 * Shortest distances from `source` to every vertex.
 *
 * @param {Edge[][]} graph adjacency list: graph[u] lists the edges leaving vertex u
 * @param {number} source the start vertex, 0 <= source < graph.length
 * @returns {{ dist: number[], prev: number[] }}
 *   dist[v]: length of the shortest path source → v (Infinity when v cannot be reached);
 *   prev[v]: the vertex just before v on that path (-1 for the source and unreachable vertices)
 */
export function dijkstra(graph, source) {
  const dist = new Array(graph.length).fill(Infinity);
  const prev = new Array(graph.length).fill(-1);
  const queue = new MinHeap();

  dist[source] = 0;
  queue.push([0, source]);

  while (queue.size > 0) {
    const [distance, u] = queue.pop();
    // Lazy deletion: u may sit in the queue several times. Only its best entry counts.
    if (distance > dist[u]) continue;

    for (const [v, weight] of graph[u]) {
      const candidate = distance + weight;
      if (candidate < dist[v]) {
        // Relax the edge u → v: going through u is shorter than anything seen so far.
        dist[v] = candidate;
        prev[v] = u;
        queue.push([candidate, v]);
      }
    }
  }
  return { dist, prev };
}

/**
 * Rebuilds the shortest path source → target by walking `prev` backwards from the target.
 *
 * @param {number[]} prev the `prev` array returned by `dijkstra`
 * @param {number} source the source `dijkstra` ran from
 * @param {number} target where the path should end
 * @returns {number[]} the vertices from source to target, or [] if target cannot be reached
 */
export function shortestPath(prev, source, target) {
  const path = [];
  for (let v = target; v !== -1; v = prev[v]) path.push(v);
  path.reverse();
  return path[0] === source ? path : [];
}

# Dijkstra's algorithm: shortest distances from one source in a graph whose edge weights are all >= 0.
# A priority queue always hands us the closest vertex we have not finished yet — and with no
# negative edges, nothing found later can beat that distance, so it is final.
import heapq
import math
from typing import List, Tuple

# Adjacency list: graph[u] lists the edges leaving u as (to, weight) pairs, weight >= 0.
Graph = List[List[Tuple[int, int]]]


def dijkstra(graph: Graph, source: int) -> Tuple[List[float], List[int]]:
    """Return (dist, prev) for every vertex.

    dist[v]: length of the shortest path source -> v (math.inf when v cannot be reached).
    prev[v]: the vertex just before v on that path (-1 for the source and unreachable vertices).
    """
    dist: List[float] = [math.inf] * len(graph)
    prev = [-1] * len(graph)
    dist[source] = 0
    # heapq keeps the smallest (distance, vertex) tuple first; ties go to the smaller vertex.
    queue: List[Tuple[float, int]] = [(0, source)]

    while queue:
        distance, u = heapq.heappop(queue)
        # Lazy deletion: u may sit in the queue several times. Only its best entry counts.
        if distance > dist[u]:
            continue

        for v, weight in graph[u]:
            candidate = distance + weight
            if candidate < dist[v]:
                # Relax the edge u -> v: going through u is shorter than anything seen so far.
                dist[v] = candidate
                prev[v] = u
                heapq.heappush(queue, (candidate, v))
    return dist, prev


def shortest_path(prev: List[int], source: int, target: int) -> List[int]:
    """Rebuild the path source -> target by walking prev backwards from the target.

    Return the vertices from source to target, or [] if target cannot be reached.
    """
    path = []
    v = target
    while v != -1:
        path.append(v)
        v = prev[v]
    path.reverse()
    return path if path[0] == source else []

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * Dijkstra's algorithm: shortest distances from one source in a graph whose edge weights are all >= 0.
 * A priority queue always hands us the closest vertex we have not finished yet — and with no
 * negative edges, nothing found later can beat that distance, so it is final.
 */
public final class Dijkstra {
    /** dist[v] for a vertex the source cannot reach. */
    public static final long UNREACHABLE = Long.MAX_VALUE;

    /** An edge to vertex {@code to}, with weight >= 0. The graph is a list of these per vertex. */
    public record Edge(int to, int weight) {
    }

    /**
     * dist[v]: length of the shortest path source → v ({@link #UNREACHABLE} when there is none).
     * prev[v]: the vertex just before v on that path (-1 for the source and unreachable vertices).
     */
    public record Result(long[] dist, int[] prev) {
    }

    /** A queue entry. Ties on distance go to the smaller vertex, so the result is deterministic. */
    private record Entry(long dist, int vertex) {
    }

    private static final Comparator<Entry> CLOSEST_FIRST =
            Comparator.comparingLong(Entry::dist).thenComparingInt(Entry::vertex);

    private Dijkstra() {
    }

    /** Shortest distances from source to every vertex of graph (an adjacency list). */
    public static Result dijkstra(List<List<Edge>> graph, int source) {
        long[] dist = new long[graph.size()];
        int[] prev = new int[graph.size()];
        Arrays.fill(dist, UNREACHABLE);
        Arrays.fill(prev, -1);
        PriorityQueue<Entry> queue = new PriorityQueue<>(CLOSEST_FIRST);

        dist[source] = 0;
        queue.add(new Entry(0, source));

        while (!queue.isEmpty()) {
            Entry entry = queue.poll();
            int u = entry.vertex();
            // Lazy deletion: u may sit in the queue several times. Only its best entry counts.
            if (entry.dist() > dist[u]) {
                continue;
            }

            for (Edge edge : graph.get(u)) {
                long candidate = entry.dist() + edge.weight(); // long: sums of ints can overflow int
                if (candidate < dist[edge.to()]) {
                    // Relax the edge u → v: going through u is shorter than anything seen so far.
                    dist[edge.to()] = candidate;
                    prev[edge.to()] = u;
                    queue.add(new Entry(candidate, edge.to()));
                }
            }
        }
        return new Result(dist, prev);
    }

    /**
     * Rebuilds the path source → target by walking prev backwards from the target.
     * Returns the vertices from source to target, or an empty list if target cannot be reached.
     */
    public static List<Integer> shortestPath(int[] prev, int source, int target) {
        List<Integer> path = new ArrayList<>();
        for (int v = target; v != -1; v = prev[v]) {
            path.add(v);
        }
        Collections.reverse(path);
        return path.get(0) == source ? path : List.of();
    }
}

// Dijkstra's algorithm: shortest distances from one source in a graph whose edge weights are all >= 0.
// A priority queue always hands us the closest vertex we have not finished yet — and with no
// negative edges, nothing found later can beat that distance, so it is final.
#include <algorithm>
#include <functional>
#include <limits>
#include <queue>
#include <utility>
#include <vector>

// An edge to vertex `to`, with weight >= 0.
struct Edge {
    int to;
    int weight;
};

// Adjacency list: graph[u] lists the edges leaving vertex u.
using Graph = std::vector<std::vector<Edge>>;

// dist[v] for a vertex the source cannot reach.
constexpr long long UNREACHABLE = std::numeric_limits<long long>::max();

// dist[v]: length of the shortest path source -> v (UNREACHABLE when there is none).
// prev[v]: the vertex just before v on that path (-1 for the source and unreachable vertices).
struct ShortestPaths {
    std::vector<long long> dist;
    std::vector<int> prev;
};

ShortestPaths dijkstra(const Graph& graph, int source) {
    ShortestPaths result{std::vector<long long>(graph.size(), UNREACHABLE), std::vector<int>(graph.size(), -1)};
    std::vector<long long>& dist = result.dist;
    std::vector<int>& prev = result.prev;

    // (distance, vertex) pairs; std::greater turns the max-heap into a min-heap.
    // Ties on distance go to the smaller vertex, so the result is deterministic.
    using Entry = std::pair<long long, int>;
    std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> queue;

    dist[source] = 0;
    queue.push({0, source});

    while (!queue.empty()) {
        auto [distance, u] = queue.top();
        queue.pop();
        // Lazy deletion: u may sit in the queue several times. Only its best entry counts.
        if (distance > dist[u]) {
            continue;
        }

        for (const Edge& edge : graph[u]) {
            long long candidate = distance + edge.weight;  // long long: sums of ints can overflow int
            if (candidate < dist[edge.to]) {
                // Relax the edge u -> v: going through u is shorter than anything seen so far.
                dist[edge.to] = candidate;
                prev[edge.to] = u;
                queue.push({candidate, edge.to});
            }
        }
    }
    return result;
}

// Rebuilds the path source -> target by walking prev backwards from the target.
// Returns the vertices from source to target, or an empty vector if target cannot be reached.
std::vector<int> shortestPath(const std::vector<int>& prev, int source, int target) {
    std::vector<int> path;
    for (int v = target; v != -1; v = prev[v]) {
        path.push_back(v);
    }
    std::reverse(path.begin(), path.end());
    if (path.front() != source) {
        return {};
    }
    return path;
}