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

Question

Я понимаю, что такое алгоритм Дейкстры , но я не понимаю, почему он работает.

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

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 - никаких улучшений пока нет. Это оставляет нас с

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

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

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

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

Answer 3

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

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

Answer 4

Чтобы понять основную идею этого алгоритма, я написал этот код для вас. Есть объяснение того, как это работает.

graph = {}

graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"] = {}
graph["a"]["finish"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["finish"] = 5
graph["finish"] = {}

infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["finish"] = infinity
print "The weight of each node is: ", costs

parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["finish"] = None

processed = []

def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

node = find_lowest_cost_node(costs)
print "Start: the lowest cost node is", node, "with weight",\
    graph["start"]["{}".format(node)]

while node is not None:
    cost = costs[node]
    print "Continue execution ..."
    print "The weight of node {} is".format(node), cost
    neighbors = graph[node]
    if neighbors != {}:
        print "The node {} has neighbors:".format(node), neighbors
    else:
        print "It is finish, we have the answer: {}".format(cost)
    for neighbor in neighbors.keys():
        new_cost = cost + neighbors[neighbor]
        if costs[neighbor] > new_cost:
            costs[neighbor] = new_cost
            parents[neighbor] = node
    processed.append(node)
    print "This nodes we researched:", processed
    node = find_lowest_cost_node(costs)
    if node is not None:
        print "Look at the neighbor:", node

# to draw graph
import networkx
G = networkx.Graph()
G.add_nodes_from(graph)
G.add_edge("start", "a", weight=6)
G.add_edge("b", "a", weight=3)
G.add_edge("start", "b", weight=2)
G.add_edge("a", "finish", weight=1)
G.add_edge("b", "finish", weight=5)

import matplotlib.pyplot as plt
networkx.draw(G, with_labels=True)
plt.show()

Answer 5

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

Answer 6

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

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 7

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

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

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

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

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

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

2) Предположим, что P равно k, число элементов P соответствует приведенному выше определению, см. Алгоритм ниже третьего шага

3) P in и первый обнаруженный не отмечен минимальной вершиной 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).

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

On i) S, P1, P2 ... Pn, U, V = L (U) + W (U, V)

ii) S, P1, P2 ... Pn, V = L (V)

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

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

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

Вот источник .