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

Question

Я понимаю, что такое Dijkstra's algorithm, но я не понимаю, почему он работает.

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

Answer 1

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

v0 <= v1 <= v2 <= v3 ... 

Может ли быть более дешевым способом добраться до вершины v1? Если это так, путь должен пройти v0, так как непроверенная вершина может быть ближе. Итак, вы проверяете вершину v0, чтобы узнать, где вы можете добраться, проверяя, есть ли какой-либо путь через v0 (любой другой вершине в один шаг).

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

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

Давайте рассмотрим краткий пример. Предположим, мы пытаемся получить от 1 до 12 умножением, а стоимость между узлами - это номер, который вы должны умножить на. (Мы будем ограничивать вершины к номерам от 1 до 12.)

Мы начинаем с 1, и мы можем добраться до любого другого узла путем умножения этого значения. Таким образом, узел 2 имеет стоимость 2, 3 имеет стоимость 3, ... 12 имеет стоимость 12, если вы идете одним шагом.

Теперь путь через 2 может (не зная о структуре) добраться до 12 быстро, если был свободный ссылка с 2 на 12. Нет, но если бы это было, это было бы быстрее всего. Итак, мы проверяем 2. И мы находим, что мы можем добраться до 4 по цене 2, до 6 за 3 и так далее.Таким образом, мы имеем таблицу затрат как так:

3 4 5 6 7 8 9 10 11 12 // Vertex 
3 4 5 5 7 6 9 7 11 8 // Best cost to get there so far. 

Хорошо, теперь, может быть, мы можем получить 12 от 3 бесплатно! Лучшая проверка. И мы находим, что 3*2==6, поэтому стоимость до 6 составляет 3 плюс 2, а также 9 - это плюс 3, а 12 - плюс 4.

4 5 6 7 8 9 10 11 12 
4 5 5 7 6 6 7 11 7 

Ярмарка достаточно. Теперь мы тестируем 4, и мы видим, что мы можем добраться до 8 за дополнительные 2 и до 12 за дополнительные 3. Опять же, стоимость, чтобы добраться до 12, таким образом, не более чем 4 + 3 = 7:

5 6 7 8 9 10 11 12 
5 5 7 6 8 7 11 7 

Теперь попробуйте 5 и 6 --no улучшения до сих пор. Это оставляет нас с

7 8 9 10 11 12 
7 6 8 7 11 7 

Теперь, в первый раз, мы видим, что затраты на получение в 8 является менее, чем стоимость добраться до 7, так что нам лучше проверить, что там не какой-то бесплатный способ добраться до 12 от 8. Нет - нет никакого способа добраться туда с целыми числами, поэтому мы выбросим его.

7 9 10 11 12 
7 8 7 11 7 

И теперь мы видим, что 12 как дешево, как покинул любой путь, поэтому стоимость достичь 12 должна быть 7. Если бы мы до сих пор отслеживали самый дешевый путь (только заменяя путь, когда он будет лучше), мы обнаружим, что 3*4 - первый самый дешевый способ попасть в 12.

Answer 2

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

Посещение любой другой вершины, поэтому, если она более дорогостоящая (что вполне возможно), необходимо посещать не только эту другую вершину, но и ту, которая имеет наименьшую стоимость пути, поэтому вам придется посетить больше вершины, прежде чем найти кратчайший путь. Фактически, если вы это сделаете, вы получите Bellman-Ford algorithm.

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

Answer 3

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

Алгоритм Дейкстры, G от S ко всем вершинам кратчайшей длины пути. Предположим, что каждой вершине G в V задан флаг L (V), либо либо число, либо ∞. Предположим, что P - множество вершин из G, P содержит S, чтобы удовлетворить:

A) Если V - это P, то L (V) от VS до длины кратчайшего пути и существование такого V из S к кратчайшему пути: путь к вершинам в P в

B) Если V не принадлежит P, то L (V) от S до V удовлетворяет следующим ограничениям на длину кратчайшего пути: V является единственный путь P не принадлежит вершине.

Мы можем использовать индукцию, чтобы доказать, алгоритм Р Дейкстры в соответствии с приведенным выше определением коллекции:

1) Когда число элементов в P = 1, Р соответствует первому шагу в алгоритме, P = (S), очевидно, выполняется.

2) Пусть Р к, число элементов, Р удовлетворяют приведенному выше определению, см алгоритм ниже третьего шага

3) Р в и первым, чтобы узнать, не маркирован с минимальной вершиной U, обозначенный как L (U), можно доказать из S в U U за пределами кратчайшего пути, в дополнение к P не содержит элементов, которые не принадлежат.

Потому что, если за пределами других вершин, кроме U, существует кратчайший путь к S, P1, P2 ... Pn, Q1, Q2 ... Qn, U (P1, P2 ... Pn - P; Q1, Q2, ... Qn не принадлежит P), по характеру B) кратчайшая длина пути L (Q1) + PATH (Q1, U)> L (U).

, который больше, чем S, P1, P2 ... Pn, U длины канала L (U), не является самым коротким путем. Следовательно, от S до U U за пределами кратчайшего пути помимо P не содержит элементов, не принадлежащих U из S, к длине кратчайшего пути из L (U).

U добавляется к P в форме P ', очевидно, P' для удовлетворения характера A).

Take V не принадлежит P ', очевидно, не принадлежит VP, то от S до V, за исключением кратчайшего пути и удовлетворяющего всем вершинам вне V в P' на пути, есть две возможности: i) содержит U, II) не содержит U.

На I) С, Р1, Р2 ... Рп, U, V = L (U) + W (U, V)

II) С, Р1 , P2 ... Pn, V = L (V)

Очевидно, что два задаются в наименьшем V из S, чтобы соответствовать минимальному доступу, а внешнее дополнение ко всем вершинам имеет длину VP '.

Третий шаг к алгоритму, заданному в P 'с элементами k +1 и встречающими A), B).

По индукции предложение может разрешить.

Адрес the source.

Answer 4

Причина, почему алгоритм Dijsktra работает так, как это делает в части, поскольку он использует тот факт, что самый короткий путь между узлом u и w, который включает в себя точку v также содержит кратчайший путь от u к v и от v к w. Если между u и v существует что-то меньшее, то это не будет самый короткий путь.

Чтобы понять, почему работает алгоритм Дейкстры, изучите основы dynamic programming, звучит сложно, но это очень легко понять принципы.

Answer 5

Он сначала проверяет путь с самым низким весом, потому что это наиболее вероятно (без дополнительной информации), чтобы уменьшить количество проверенных путей. Например:

 
a->b->c  cost is 20 
a->b->d  cost is 10 
a->b->d->e cost is 12 

Если цель состоит в том, чтобы получить от е, мы не должны даже проверить стоимость:

 
a->b->c->e 

Потому что мы знаем, что по крайней мере 20, поэтому мы знаем, что это не является оптимальным, потому что есть уже другой путь со стоимостью 12. Вы можете максимизировать этот эффект, сначала проверив самые низкие веса. Это похоже (так же?) На то, как минимакс работает в шахматах и ​​других играх, чтобы уменьшить коэффициент ветвления дерева игры.

Answer 6

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