Я правильно думаю об этом отрицательном весе, используя график алгоритма Дейкстры?

Question

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

Я был бы прав, считая, что; первый A. A->B будет 1 и A->C будет 100. Затем исследуется B и устанавливает B->D на 2. Затем обрабатывается D, поскольку в настоящее время он имеет самый короткий путь к источнику (т. Е. В верхней части очереди приоритетов)?

Я был бы прав, говоря, что если B->D был 100, C бы уже были изучены первые (с A->D является 101)?

Единственное, что люди не упоминали в каждом объяснении, заключалось в том, что узел был исследован/посещен, он больше не может быть обновлен, поскольку Dijkstra работает в очереди приоритетов. Мне просто трудно обернуть голову вокруг, почему D посещают до C в этом случае.

Answer 1

Это просто: когда узел с использованием алгоритма Djikstra в разведано/посетили/закрыто это означает, что вы нашли кратчайший путь к этому узлу, поэтому этот узел не должен быть reexplored или повторно, вы уже знать кратчайший путь к узлу.

Например, при выборе D, чтобы изучить есть два пути в Рф:

• ABD с ценой 2
• переменного тока со стоимостью 100

и путь с наименьшим выбирается стоимость. Тогда, очевидно, что если затраты на дуги всегда положительные, вы не можете найти кратчайший путь к D, проходящий через A-C. Найден самый короткий путь к D, и узел закрыт.

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

Answer 2

Я думаю, что алгоритм Дейкстры, который вы описываете, действует только на положительные весовые функции. В частности, алгоритм Дейкстры дает действительную структуру метрического пространства на каждом взвешенном (положительном) графе. С другой стороны, это не относится к произвольным взвешенным графам. Возьмем, например, график с двумя узлами A и B и одним ребром между ними с весом -5. В этом случае это не даст расстояния между A и B. То, что вы описываете, я думаю, попадет в какую-то модифицированную модель Дийкстры, а интерпретация перехода от одного узла к другому уже не может быть интерпретирована как расстояние между узлами ,