Окончательные
В очереди
Проверенные ребра

  • Текущая
  • В очереди
  • Окончательные
  • Путь
Щелчок по вершине задает

Подробнее об алгоритме Дейкстры

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

Алгоритм Дейкстры находит кратчайший маршрут от старта до каждой другой вершины, когда у ребер есть длины, как у дорог между городами. Он растет от старта наружу и всегда берет ближайшую вершину, которую еще не завершил. Щелкните вершину, чтобы начать с нее, при желании выберите цель и пройдите по шагам, чтобы увидеть очередь, как уменьшается каждое расстояние, когда находятся более короткие пути, и как появляется кратчайший путь. Нажмите Пуск, чтобы посмотреть поиск, или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место. Щелкните вершину, чтобы сделать ее стартом; переключите щелчок на Цель и щелкните другую вершину, чтобы искать кратчайший путь к ней. Число на каждом ребре — его длина, число на каждой вершине — ее кратчайшее расстояние на данный момент, а ряд под графом — это очередь, ближайшие первыми. Кнопка Новый граф создает другой граф; выберите, сколько в нем вершин и ребер. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят в начало и в конец.

Как это работает

  1. Щелкните вершину, чтобы сделать ее стартом. Чтобы искать путь, переключите щелчок на Цель и щелкните другую вершину.
  2. Нажмите Пуск или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место поиска.
  3. Следите за очередью под графом и расстоянием на каждой вершине. Кнопка Новый граф создает другой граф для пробы.

Как работает алгоритм Дейкстры

Задайте старту расстояние 0, а всем остальным вершинам — бесконечность, и поместите старт в очередь. Затем повторяйте: возьмите из очереди вершину с наименьшим расстоянием и отметьте это расстояние как окончательное. Для каждого ее соседа, чье расстояние еще не окончательное, прибавьте длину ребра к расстоянию вершины. Если сумма меньше текущего расстояния соседа, она становится новым расстоянием, вершина запоминается как путь к соседу, а сосед встает в очередь, если его там не было. Когда очередь пуста, у каждой достижимой вершины есть кратчайшее расстояние.

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

Когда вершина ближайшая в очереди, любой другой путь к ней должен покинуть завершенную часть графа через какую-то вершину в очереди, которая находится не ближе, а затем добавить ребра, которые не могут быть отрицательными. Поэтому никакой другой путь не может быть короче. По той же причине цель известна наверняка, только когда она взята из очереди, а не когда она впервые достигнута, и поэтому алгоритм Дейкстры не работает с отрицательными ребрами: для них нужен алгоритм Беллмана — Форда. Когда у каждого ребра длина 1, алгоритм Дейкстры делает то же, что и поиск в ширину.

Часто задаваемые вопросы

Что такое алгоритм Дейкстры?

Способ найти кратчайшие пути от одной стартовой вершины до всех остальных вершин в графе, длины ребер которого равны нулю или больше. Он раз за разом берет ближайшую незавершенную вершину, делает ее расстояние окончательным и с помощью ее ребер сокращает расстояния до соседей.

Почему алгоритм Дейкстры не работает с отрицательными ребрами?

Он делает расстояние вершины окончательным, как только эта вершина становится ближайшей в очереди. Отрицательное ребро, найденное позже, могло бы привести к этой вершине более коротким путем, и окончательное расстояние оказалось бы неверным. Алгоритм Беллмана — Форда справляется с отрицательными ребрами, если нет цикла с отрицательной суммой.

Чем Дейкстра отличается от BFS?

Поиск в ширину считает ребра и использует обычную очередь. Алгоритм Дейкстры складывает длины ребер и использует очередь с приоритетом, которая всегда выдает ближайшую вершину. Если у каждого ребра длина 1, оба находят одинаковые расстояния.

Насколько быстр алгоритм Дейкстры?

С двоичной кучей в качестве очереди с приоритетом работа растет как (V + E) log V для V вершин и E ребер. С фибоначчиевой кучей — как E + V log V. Приложение хранит очередь как отсортированный список: его легко показать, и для небольших графов этого достаточно.

Отправляется ли мой граф куда-нибудь?

Нет. Граф создается и обходится в вашем браузере, а последние настройки хранятся в локальном хранилище этого браузера.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Перейти в редактор