Вариации алгоритма расстановки меток

 

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

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

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

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

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

поиск возможных узлов.

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

 

Коррекция меток

 

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

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

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

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

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

Алгоритм коррекции меток всегда выбирает первый узел из списка возможных, который не всегда является лучшим выбором. Значения полей Dist и InLink данного узла могут и не быть лучшими возможными значениями. Но в конце концов алгоритм отыщет в списке узел, через который проходит более короткий путь к выбранному узлу. Тогда алгоритм обновляет поля Dist и InLink неправильно выбранного узла и помещает этот узел обратно в список возможных.

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

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

 

Варианты алгоритма коррекции меток

 

Данный алгоритм позволяет быстро выбирать узлы из списка возможных. Он может также добавлять узел в список всего за один или два шага. Недостаток алгоритма коррекции меток состоит в том, что когда он выбирает узел из списка возможных, этот выбор не всегда оказывается удачным. Если алгоритм выбирает узел до того, как поля Dist и InLink этого узла получат свои конечные значения, он должен потом исправить значения этих полей и снова поместить узел в список возможных. Чем чаще алгоритм помещает узлы назад в список, тем больше времени занимает его выполнение.

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

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

 

Варианты поиска кратчайшего пути

 

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