Вступление
Мы уже знаем, как найти кратчайшие пути в графе, начиная с данной вершины. Практически мы модифицировали поиск в ширину, чтобы вычислить расстояния от s до всех других узлов, доступных из s. Мы знаем, что это работает, потому что BFS проходит по графику уровень за уровнем.
BFS часто используется для поиска кратчайших путей между начальным узлом (ами) и всеми другими достижимыми узлами в графе!
Некоторые источники дают очень простое объяснение того, как BFS находит кратчайшие пути в графе. Мы должны просто думать о графике как о наборе шаров, соединенных через строки.
Мы можем представить граф как набор шаров, соединенных через строки!
Как мы видим, подняв шар под названием «S», все остальные шары падают. Ближайшие шары напрямую связаны с «s», и это первый уровень, в то время как самые внешние шары — те, у которых самые длинные пути.
Поиск в ширину работает так же, как на картинке выше — он исследует уровень графика за уровнем, поэтому мы уверены, что все пути самые короткие!
Очевидно, что ребра, такие как между A и B, не имеют значения для нашего алгоритма BFS, потому что они не делают путь от S до C через B короче. Это также известно как неравенство треугольника, где сумма длин двух сторон треугольника всегда больше, чем длина третьей стороны.
Что говорит нам неравенство треугольника, так это то, что если у нас есть прямое ребро между двумя узлами — это должен быть кратчайший путь между ними!
Мы должны только ответить на вопрос, является ли BFS лучшим алгоритмом, который находит кратчайший путь между любыми двумя узлами графа? Это разумный вопрос, потому что, как мы знаем, используя BFS, мы не находим только кратчайший путь между заданными вершинами i и j, но мы также получаем кратчайшие пути между i и всеми остальными вершинами G. Это информация, которую мы на самом деле не нужно, но можем ли мы найти кратчайший путь между i и j без этой информации?
Ответ просто «нет»! Практически поиск в глубину не может помочь нам. Еще хуже — мы можем найти пути, которые далеко не самые короткие.
DFS на самом деле может найти самый длинный путь в некоторых случаях и не может быть использован для поиска самого короткого пути!
На изображении выше с использованием DFS расстояние между 1 и 7 составляет 7, в то время как между ними практически есть грань.
Таким образом, BFS является оптимальным алгоритмом для поиска кратчайших путей в графе. Но есть подвох! Этот алгоритм работает хорошо, когда мы предполагаем, что все ребра имеют одинаковую длину. В приведенных выше примерах каждое ребро имеет значение 1. Таким образом, N ребер между s и i сделали расстояние между ними длины N.
обзор
Как мы знаем на практике, разные ребра могут иметь разные значения. Именно это было в случае взвешенных графиков. Возвращаясь к примеру с дорожной картой, расстояния между разными городами обычно оцениваются в милях или километрах. Конечно, мы можем связать любое другое значимое значение с этими краями. Это может быть время в часах, чтобы путешествовать между городами, деньги на топливо или что-то еще.
На практике чаще используют взвешенные графы, чем невзвешенные!
Теперь BFS больше не может нам помочь. Зачем? Поскольку использование неравных значений для ребер, неравенство треугольника больше не верно. Теперь ребро (прямой путь) между A и B может быть больше, чем сумма двух ребер (A, C) + (C, B)!
В взвешенном графике ребра не равны для нашего алгоритма BFS, поэтому мы не можем его использовать!
Другими словами, предполагая ту же абстракцию с шарами и проводами, подвесные провода не могут быть отброшены так легко.
На взвешенных графиках BFS больше не полезен!
Итак, как мы можем решить эту проблему? Очень глупый подход — разбить каждое ребро фиктивными вершинами, чтобы заставить BFS снова работать.
Поскольку граф взвешен, мы можем разложить его ребра на более «фиктивные» ребра!
Однако у этого подхода есть несколько слабых мест. Основным из них является то, что нам придется хранить гораздо больше информации, что означает большее использование памяти, даже для небольших графиков. Это делается в случае, если мы разбиваем каждое ребро на слишком много частей.
Решение этой проблемы было дано Эдсгером Дейкстрой в 1956 году и опубликовано в 1959 году. Единственное, что мы должны сейчас сделать, — это быть уверенным, что даже отбрасывая неравенство треугольника, мы имеем кратчайшие пути. Первое, что нужно сделать, это сохранить информацию о расстоянии от s до родительского (предыдущего) узла i в графе, чтобы вычислить, какое расстояние короче.
В BFS мы использовали очередь, чтобы пройти через всех предков узла. Это было сделано последовательно. Таким образом, для графа G на следующем изображении порядок постановки в очередь предков S был A, B, C.
Порядок постановки в очередь в BFS является последовательным — то, что не работает для взвешенных графов!
Алгоритм Дейкстры использует приоритетную очередь, также известную как куча. Этот факт в сочетании с тем, что мы храним информацию для кратчайшего пути, помогают нам найти кратчайшие пути в взвешенных графиках.
Почему это работает? Чтобы ответить на этот вопрос, давайте посмотрим на следующий очень простой пример, предполагая граф G из следующего изображения. Как мы видим, неравенство треугольника не соответствует действительности.
Взвешенный график, который не следует неравенству треугольника!
Хорошо, мы видим, что путь [S, B, A] короче, чем [S, A], хотя ребро (S, A) существует. Как алгоритм Дейкстры преодолевает эту проблему.
Во-первых, у нас нет информации о расстояниях (S, A) и (S, B), единственное, что мы знаем, это то, что S является начальной точкой, его расстояние равно 0, а его путь пока является пустым множеством. Итак, сначала мы ставим в очередь приоритеты расстояния от S до A и B.
Алгоритм Дейкстры использует приоритетную очередь!
Теперь мы вытесняем минимальный (первый в куче) элемент из очереди — ближайший к S узел, то есть B. Затем все узлы, смежные с S в очереди, проверяются на смежность с B, таким образом, если у нас уже есть расстояние между S и A теперь мы можем проверить, больше ли (S, B) + (B, A) — неравенство треугольника!
Пока мы знаем, что нам нужно немного изменить BFS, чтобы получить алгоритм Дейкстры. Единственное, что нужно сделать, — это сохранить информацию для каждого узла для пути через его родительский узел и использовать очередь с приоритетами.
Код
Реализация этих алгоритмов не намного сложнее, чем BFS, поэтому вот код на PHP . Однако этот пример использует стандартную библиотеку php SPL и структуру данных PriorityQueue, но любой разработчик может кодировать свою собственную кучу .
Вот график из кода:
График!
class vertex
{
public $key = null;
public $visited = 0;
public $distance = 1000000; // infinite
public $parent = null;
public $path = null;
public function __construct($key)
{
$this->key = $key;
}
}
class PriorityQueue extends SplPriorityQueue
{
public function compare($a, $b)
{
if ($a === $b) return 0;
return $a > $b ? -1 : 1;
}
}
$v0 = new vertex(0);
$v1 = new vertex(1);
$v2 = new vertex(2);
$v3 = new vertex(3);
$v4 = new vertex(4);
$v5 = new vertex(5);
$list0 = new SplDoublyLinkedList();
$list0->push(array('vertex' => $v1, 'distance' => 3));
$list0->push(array('vertex' => $v3, 'distance' => 1));
$list0->rewind();
$list1 = new SplDoublyLinkedList();
$list1->push(array('vertex' => $v0, 'distance' => 3));
$list1->push(array('vertex' => $v2, 'distance' => 7));
$list1->rewind();
$list2 = new SplDoublyLinkedList();
$list2->push(array('vertex' => $v1, 'distance' => 7));
$list2->push(array('vertex' => $v3, 'distance' => 8));
$list2->push(array('vertex' => $v4, 'distance' => 12));
$list2->rewind();
$list3 = new SplDoublyLinkedList();
$list3->push(array('vertex' => $v0, 'distance' => 1));
$list3->push(array('vertex' => $v2, 'distance' => 8));
$list3->rewind();
$list4 = new SplDoublyLinkedList();
$list4->push(array('vertex' => $v2, 'distance' => 12));
$list4->push(array('vertex' => $v5, 'distance' => 3));
$list4->rewind();
$list5 = new SplDoublyLinkedList();
$list5->push(array('vertex' => $v4, 'distance' => 3));
$list5->rewind();
$adjacencyList = array(
$list0,
$list1,
$list2,
$list3,
$list4,
$list5,
);
function calcShortestPaths(vertex $start, &$adjLists)
{
// define an empty queue
$q = new PriorityQueue();
// push the starting vertex into the queue
$q->insert($start, 0);
$q->rewind();
// mark the distance to it 0
$start->distance = 0;
// the path to the starting vertex
$start->path = array($start->key);
while ($q->valid()) {
$t = $q->extract();
$t->visited = 1;
$l = $adjLists[$t->key];
while ($l->valid()) {
$item = $l->current();
if (!$item['vertex']->visited) {
if ($item['vertex']->distance > $t->distance + $item['distance']) {
$item['vertex']->distance = $t->distance + $item['distance'];
$item['vertex']->parent = $t;
}
$item['vertex']->path = array_merge($t->path, array($item['vertex']->key));
$q->insert($item["vertex"], $item["vertex"]->distance);
}
$l->next();
}
$q->recoverFromCorruption();
$q->rewind();
}
}
calcShortestPaths($v0, $adjacencyList);
// The path from node 0 to node 5
// [0, 1, 2, 4, 5]
echo '[' . implode(', ', $v5->path) . ']';
сложность
Сложность этого кода основана на сложности BFS с основным отличием в том, что мы сохраняем приоритетную очередь. Для BFS мы знали, что сложность была O (| V | + | E |), в то время как алгоритм Дейкстры имеет время выполнения O ((| V | + | E |) .log (| V |)). Это вполне естественно, поскольку сложность heapsort равна O (n.log (n))!
заявка
Поскольку базовая BFS не может помочь нам для взвешенных графов, и существует множество задач, разработанных для взвешенных графов, очевидно, что алгоритм Дейкстры может быть очень удобным. Единственное, что мы должны знать, это положительные значения ребер.
Похожие сообщения:
- Компьютерные алгоритмы: кратчайший путь в графе
- Компьютерные алгоритмы: Graph Best-First Search
- Компьютерные алгоритмы: поиск по ширине графика
- Компьютерные алгоритмы: поиск по глубине графика
- Компьютерные алгоритмы: топологическая сортировка графа