алгоритм Дейкстры
По-английски:
Это алгоритм поиска кратчайшего маршрута из точки А в точку Б.
В вычислительном отношении мы упрощаем маршрут к графу, состоящему из узлов и дуг. Каждый узел представляет промежуточную точку, в то время как каждая дуга соединяет два узла и имеет (неотрицательный) вес, представляющий стоимость прохождения между двумя узлами.
Для реализации алгоритма вам понадобятся два списка:
- закончено: набор (узел, стоимость), в котором вы вычислили минимальную стоимость, которую нужно достичь.
- работает: отсортированный список (узел, стоимость), которые были проверены.
Алгоритм:
working.addNode(Start, 0); // No cost to get to start.
for( (node, cost) = working.popHead(); node != End; (node,cost) = working.popHead())
{
// If we have already processed this node ignore it.
if (finished.find(node))
{ continue;
}
// We have just removed a node from working.
// Because it is the top of the list it is guaranteed to be the shortest route to
// the node. If there is another route to the node it must go through one of the
// other nodes in the working list which means the cost to reach it will be higher
// (because working is sorted). Thus we have found the shortest route to the node.
// As we have found the shortest route to the node save it in finished.
finished.addNode(node,cost);
// For each arc leading from this node we need to find where we can get to.
foreach(arc in node.arcs())
{
dest = arc.dest();
if (NOT (finished.find(dest)))
{
// If the node is already in finished then we don't need to worry about it
// as that will be the shortest route other wise calculate the cost and add
// this new node to the working list.
destCost = arc.cost() + cost;
working.addNode(dest,destCost); // Note. Working is sorted list
}
}
}
Так что, если вы думаете об этом алгоритме. Скажем, вы едете из Лондона в Манчестер.
finished = {} // empty.
working = { (London,0) }
Использование следующей матрицы затрат:
L S O B N M W
(L) ondon - 50 60 100 130 - -
(S) outhampton 50 - 70 - - - -
(O) xford 60 70 - 50 - 200 -
(B) irmingham 100 - 50 - - 80 110
(N) orwich 130 - - - - - -
(M) anchester - - 200 80 - - 80
Ne(W) castle - - - 110 - 80 -
Теперь вы вынимаете Лондон из рабочего списка (как он есть во главе) и помещаете его в готовый список. Затем добавьте в рабочий список все города, непосредственно связанные с Лондоном.
finished = { (London,0) }
working = { (Southampton, 50), (Oxford, 60), (Birmingham, 100), (Norwich,130) }
Рассмотрим города в рабочем наборе, внешний край пузыря которого расширился от Лондона. Задача алгоритма Дейкстры состоит в том, чтобы продолжать расширять пузырь, пока мы не достигнем Манчестера (без повторения каких-либо шагов, которые мы уже предприняли). Таким образом, пузырь всегда расширяется наружу, и мы всегда расширяем самую маленькую часть пузыря.
Итак, следующий шаг - взять заголовок списка и повторить. Из Саутгемптона есть только два пункта назначения. Вернуться в Лондон (который мы отбрасываем, как он есть в готовом списке) и Оксфорд Стоимость проезда в Оксфорд составляет 50 + стоимость от Саутгемптона до Оксфорда (поэтому обратите внимание, что он дважды находится в рабочем списке, но не волнуйтесь, позже мы откажемся от него, так как это не оптимальный маршрут).
finished = { (London,0), (Southampton,50) }
working = { (Oxford, 60), (Birmingham, 100), (Oxford, 120), (Norwich,130) }
Так повторите цикл. Главой списка является Оксфорд. Из Оксфорда мы можем поехать в Манчестер (200), Бирмингем (50) или обратно в Лондон (60) или Саутгемптон (помните, что нам нужно добавить стоимость проезда в Оксфорд к каждой из этих затрат выше. отправился в Саутгемптон, но мы уже нашли кратчайший путь в Саутгемптон, поэтому обработка не требуется). Это оставит нас с:
finished = { (London,0), (Southampton,50), (Oxford, 60) }
working = { (Birmingham, 100), (Birmingham,110), (Oxford, 120), (Norwich,130), (Manchester,200)}
Обратите внимание, что у нас есть Манчестер в рабочем списке (это наш пункт назначения). Но нам нужно продолжать работать, поскольку мы можем найти более короткий маршрут. Так что теперь мы расширяемся из Бирмингема. Оттуда мы можем пойти в Оксфорд (50), Манчестер (80), Лондон (100), Ньюкасл (110). Если добавить стоимость поездки в Бирмингем, это дает нам:
finished = { (London,0), (Southampton,50), (Oxford, 60), (Birmingham, 100) }
working = { (Birmingham,110), (Oxford, 120), (Norwich,130), {Manchester, 180), (Manchester,200), (Newcastle, 210)}
Следующие два узла. Оксфорд и Бирмингем уже в готовом списке, поэтому мы можем их игнорировать. Таким образом, если нет маршрута из Норвича в Манчестер, который составляет менее 50 миль, мы доберемся до Манчестера в итерации после этого.