Алгоритм Дейкстры

O(E log V)

Храним лучшую известную стоимость для каждого узла, на каждом шаге фиксируем самый дешёвый ещё не зафиксированный узел и релаксируем его рёбра, снижая стоимость соседей. Поскольку все веса неотрицательны, стоимость узла становится окончательной в момент его фиксации.

Сигналы

самый дешёвый/короткий путь со взвешенными рёбраминеотрицательные веса рёберминимальная суммарная стоимость до каждого узлазадержка в сети / стоимость маршрута, а не число дорогвзвешенный граф, кратчайшие пути из одного источника

Шаблон

function dijkstra(n, adj, source) {
    const dist = new Array(n).fill(Infinity);
    dist[source] = 0;
    const heap = [[0, source]]; // [distance, node]
    while (heap.length) {
        heap.sort((a, b) => a[0] - b[0]); // swap for a real heap in production
        const [d, u] = heap.shift();
        if (d > dist[u]) continue;
        for (const [v, w] of adj[u] || []) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                heap.push([dist[v], v]);
            }
        }
    }
    return dist;
}

Похоже, но не то

Обход графа BFS / DFS: BFS считает шаги в невзвешенном графе, считая все рёбра одинаковыми по цене. Дейкстра нужен для взвешенных неотрицательных рёбер, где три дешёвых ребра могут обойти два дорогих, поэтому просто число рёбер здесь не ответ.

V, E до ~1e5, неотрицательные веса рёбер, нужен самый дешёвый путь, а не минимум рёбер -> O(E log V) с мин-кучей, фиксирующей один узел за извлечение.

Изучить этот паттерн