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

задняя часть PHP алгоритм GitHub

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

К методам нахождения кратчайшего пути относятся методы Дейкстры, Флойда, BFS и др. Среди них Floyd подходит для поиска кратчайших путей с несколькими источниками, а BFS подходит для случаев без весов.Эта задача относится к методам поиска кратчайших путей с одним источником, поэтому мы использовать алгоритм Дейкстры.

Поехали! Вынуть карточку метро — это картина, и теперь мы абстрагируем проблему отЦентр Баоань - Старая улицасамый короткий путь

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

найденоколлекция

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

   // 初始时,我们已知的就只有宝安中心到宝安中心的最短路径
   $found = ['宝安中心'];

дист-коллекция

Он используется для хранения кратчайшего пути от начальной точки (центра Баоань) до некоторой вершины u относительно S. Популярное объяснение таково: центр Баоань к Окну Мира проходит через Синьань, тогда должен быть Синьань ∈ S. В противном случае мы не можем напрямую узнать его относительный кратчайший путь, а в dist он записывается как невозможно большое значение, которое используется для обозначения того, что мы еще не смогли исследовать эту точку.

Кратчайший путь, хранящийся в dist, называется кратчайшим путем относительно S. Здесь и далее мы ссылаемся просто на относительный кратчайший путь, и соответственно имеем глобальный кратчайший путь

Инициализировать коллекцию dist

const MAX = 65525; //65525是我们定义的一个不可能出现的大值

 $dist = [
     '深圳北站' => 5,
     '新安' => 8,
     '世界之窗' => MAX,
     '福田' => MAX,
     '购物公园' => MAX,
     '老街' => MAX,
     '布吉' => MAX,
 ];

Алгоритм Описание

Запускаем наш алгоритм ~ мы сначала находимdistминимальное значение , здесь深圳北站 => 5.

Кстати, у нас есть для вас замечательная новость: мы нашли кратчайший в мире маршрут от центра Баоань до Северного железнодорожного вокзала Шэньчжэня.

что?Почему минимальное значение в dist является глобальным кратчайшим путем, который мы ищем (здесь宝安中心-深圳北站)? То, что мы ищем, не宝安中心-老街Знаете ли вы глобальный кратчайший путь ?宝安中心-深圳北站Какая польза от кратчайшего пути? Я не могу дать вам хорошее объяснение прямо сейчас, давайте двигаться дальше.

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

Теперь, когда найдена еще одна глобальная вершина кратчайшего пути, мы обновляем ее доfoundв коллекции

$found = ['宝安中心', '深圳北站'];

После добавления одного элемента в найденное множество наше поле зрения становится шире. мы можем пройти深圳北站как транзитное обновлениеdistэтоотносительно кратчайший путьсобранный

Через транзитную станцию ​​Северного железнодорожного вокзала Шэньчжэня мы можем пройти относительно кратчайший путь.

宝安中心-深圳北站-新安 = 5 + 2 = 7 宝安中心-深圳北站-福田 = 5 + 5 = 10 宝安中心-深圳北站-布吉 = 5 + 10 = 15

Вы можете заменить нас сейчасdistЕсть ли ценности в коллекции? Не волнуйтесь, нам нужен относительно кратчайший путь, не только кошка или собака могут пройти. Поэтому нам нужно провести сравнение.

// 如果新的相对最短路径比原有的相对最短路径要小，我们则进行一个更新
if ($newWeight < $dist['新安']) {
    $dist['新安'] = $newWeight;
}

distКоллекция обновляется следующим образом

$dist = [
     '深圳北站' => 5, // ok
     '新安' => 7, //8 -> 7
     '世界之窗' => MAX,
     '福田' => 10, // MAX -> 10
     '购物公园' => MAX,
     '老街' => MAX,
     '布吉' => 15 // MAX -> 15
 ];

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

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

Для ясности, для относительно кратчайшего пути, который еще не исследован, сначала скройте значение его веса.

после обновленияfoundа такжеdistследующим образом

$found = ['宝安中心', '深圳北站','新安'];

$dist = [
     '深圳北站' => 5, // ok
     '新安' => 7, // ok
     '世界之窗' => 16, // MAX -> 16 = 9+7 = 宝安->新安 + 新安->世界之窗
     '福田' => 10, // MAX -> 10
     '购物公园' => MAX,
     '老街' => MAX,
     '布吉' => 15
 ];

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

Обновленные s и dist следующие:

$found = ['宝安中心', '深圳北站', '新安', '福田'];

$dist = [
     '深圳北站' => 5, // ok
     '新安' => 7, // ok
     '世界之窗' => 16,
     '福田' => 10, // ok
     '购物公园' => 12, // MAX -> 12
     '老街' => 15, // MAX -> 15
     '布吉' => 15
 ];

цикл снова ↓

Обновленные значения found и dist следующие:

$s = ['宝安中心', '深圳北站', '新安', '福田', '购物公园'];

$dist = [
     '深圳北站' => 5, // ok
     '新安' => 7, // ok
     '世界之窗' => 16,
     '福田' => 10, // ok
     '购物公园' => 12, // ok
     '老街' => 15,
     '布吉' => 15
 ];

При повторном поиске минимального значения в dist мы нашли нашу цель, Laojie.

Описание алгоритма завершено!

Реализация алгоритма

GitHub.com/Неслыханно/Ах…

Анализ правильности

Почему минимальное значение в dist задает глобальный кратчайший путь, который мы ищем?

$dist = [
     '福田' => 10, // ok
     '购物公园' => 12,
     '老街' => 15,
 ];

Возьмите в качестве примера часть данных набора dist, опишите его по алгоритму宝安中心-福田-购物公园— это глобальный кратчайший путь, который мы ищем. Теперь мы предполагаем, что宝安中心-购物公园Если есть более короткий путь, возможны два случая:

Дело 1

Красная область представляет найденный набор, что означает, что набор вершин, для которого был найден глобальный кратчайший путь. Как упоминалось выше, набор dist хранит кратчайший путь относительно S.

В этом случае алгоритм уже определил, когда выполняется операция обновления набора расстояний.宝安中心-福田-购物公园а также宝安中心-X-购物公园меньшие значения между ними, поэтому такая ситуация не может существовать. Перейдем к другому, более вероятному сценарию

  • Случай 2

Существует ли такой кратчайший путь? потому чтоy-购物公园Мы не исследовали расстояние, поэтому эта ситуация требует тщательного рассмотрения.

Вернемся назад во времени

На данный момент у нас есть всего 5 вершин в нашем наборе dist. Среди них Bao'an Center, Futian и X были добавлены к найденной коллекции. Y был найден после прохождения транзита X, а торговый парк был найден после прохождения через среднюю школу Футянь. В этот момент, согласно нашему алгоритму, в качестве следующей вершины глобального кратчайшего пути будет выбрано минимальное значение между Y и торговым парком. Здесь алгоритм выбирает торговый парк. иллюстрировать宝安中心-福田-购物公园 < 宝安中心-X-Y

вернуться к делу 2

имея宝安中心-福田-购物公园 < 宝安中心-X-Yпод помещение.宝安中心-X-Y-购物公园 < 宝安中心-福田-购物公园Можно ли установить? Если уравнение не выполняется, значит, не может быть отношения宝安中心-福田-购物公园Более короткий глобальный кратчайший путь.

Я полагаю, что вы можете с первого взгляда увидеть, выполняется ли уравнение.

Анализ правильности завершен!

Эпилог

Вы все еще можете быть удивлены, почему алгоритм Дейкстры так удивителен? Даже если мы уже знаем шаги алгоритма, проанализируем правильность алгоритма. Но все же не могу не вздохнуть, как это удалось, и как он нашел оптимальное решение?

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

О~ Кстати, у этого метода фокусировки только на оптимальном решении перед вами на самом деле есть более убедительное название — жадный алгоритм.

Категории