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

Цена маршрута

Во взвешенном графе у каждого ребра есть цена: время, расстояние или другая складываемая величина. Стоимость маршрута — сумма весов его рёбер. В этом примере рёбра проходят в обе стороны, все веса неотрицательные.

BFS минимизирует число переходов: S → A → G — два ребра, но цена 8 + 1 = 9. Дейкстра находит S → B → C → G: три ребра с ценой 1 + 1 + 2 = 4. Оба маршрута допустимы, но алгоритмы минимизируют разные величины. Если все веса равны единице, минимальная цена совпадает с минимальным числом переходов.

Выбираем минимум и улучшаем расстояния

Вначале d(S)=0, у остальных вершин — бесконечность. В границе поиска лежат обнаруженные, ещё не извлечённые вершины. Выбираем минимальное d из всей границы. При равенстве сохраняем порядок первого обнаружения, соседей смотрим в порядке рёбер входного списка.

Для соседа v текущей вершины u пробуем candidate = d(u) + weight(u,v). Если получилось меньше d(v), заменяем расстояние и предка. Это релаксация. При первом обнаружении добавляем вершину в границу, при улучшении меняем приоритет уже находящейся там вершины. Равная цена сохраняет прежнего предка.

В нашем примере A сначала обнаруживается с расстоянием 8. После выбора B маршрут S → B → A даёт цену 4. Расстояние до A уменьшается с 8 до 4, предком становится B. Нельзя пропускать вершину только потому, что она уже была обнаружена.

Почему выбранное расстояние окончательное

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

Останавливаемся при извлечении G, а не при первом обнаружении. По предкам возвращаемся к S и восстанавливаем маршрут. Если граница опустела, цель недостижима. Если старт совпадает с целью, цена равна нулю, в пути одна вершина. Нулевые веса допустимы, отрицательные проверяются и отклоняются до поиска. Суммы должны помещаться в JavaScript Number: переполнение вызывает ошибку.

Здесь используется Дейкстра с остановкой на одной цели — uniform-cost search. В отличие от Greedy он не выбирает по h, а в отличие от A* не прибавляет h. Если в A* положить h=0, приоритетом тоже станет расстояние от старта.

Что показывает плеер

Числа на рёбрах — постоянная цена, d под вершиной — лучшая пока известная стоимость от S, а не оценка до G. Фиолетовый показывает границу поиска, рамка — выбранную вершину, зелёный — восстановленный путь. Расстояния и граница также перечислены текстом под графом.

«Извлечено» считает удаления из границы, включая G. «Просмотров соседей» — просмотренные записи смежности, включая закрытых соседей; соседей G не проверяем. «Улучшений конечного расстояния» — уменьшения после первого обнаружения, без замен бесконечности числом. При восстановлении путь растёт в обратную сторону, в финале разворачивается. После достижения цели расстояния ещё не извлечённых вершин могут оставаться предварительными.

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

Стоимость этой реализации

При V вершинах и E записях смежности массив границы даёт O(V² + E) времени и O(V) рабочей памяти без графа. Поиск и удаление минимума стоят O(V), каждую вершину извлекаем не более одного раза. Двоичная куча с decrease-key может дать O((V+E) log V), но здесь минимум ищется проходом по массиву.

Визуализация создаёт одну неизменяемую копию графа размером O(V+E) и сохраняет O(V) данных на событие. Всего событий O(V+E), значит история занимает O(V(V+E)) памяти дополнительно к графу. Это цена воспроизведения, отдельная от рабочей памяти алгоритма.

Реализация на JavaScript

adjacency — массив списков {to, weight}, номера вершин — целые от 0 до V−1. Для повторения примера добавьте каждое неориентированное ребро в обе стороны в порядке входного списка. Вход не изменяется. Результат содержит путь и цену либо null. Функция работает и с ориентированным графом. Веса должны быть конечными и неотрицательными, суммы — конечными.

function dijkstra(adjacency, start, goal) {
    const n = adjacency.length;
    const valid = v => Number.isInteger(v) && v >= 0 && v < n;
    if (!valid(start) || !valid(goal)) throw Error("Invalid endpoint");
    for (const neighbors of adjacency) {
        for (const { to, weight } of neighbors) {
            if (!valid(to) || !Number.isFinite(weight) || weight < 0)
                throw Error("Expected finite nonnegative weights");
        }
    }
    const distance = Array(n).fill(Infinity);
    const parent = Array(n).fill(null);
    const settled = new Set(), open = [start];
    distance[start] = 0;
    while (open.length) {
        let best = 0;
        for (let i = 1; i < open.length; i++)
            if (distance[open[i]] < distance[open[best]]) best = i;
        const current = open.splice(best, 1)[0];
        if (current === goal) {
            const path = [];
            for (let v = goal; v !== null; v = parent[v]) path.push(v);
            return { path: path.reverse(), cost: distance[goal] };
        }
        settled.add(current);
        for (const { to, weight } of adjacency[current]) {
            const candidate = distance[current] + weight;
            if (!Number.isFinite(candidate)) throw Error("Path cost overflow");
            if (settled.has(to) || candidate >= distance[to]) continue;
            if (distance[to] === Infinity) open.push(to);
            distance[to] = candidate;
            parent[to] = current;
        }
    }
    return null;
}