Несложно о сложности. Примеры алгоритмов/Задачи/ex-dijksta-not-work-on-negative-weight — различия между версиями

Текущая версия на 06:50, 4 мая 2023

Приведите пример графа с отрицательными весами, но без циклов отрицательной длины, для которого алгоритм Дейкстры даст неправильный ответ.

@@ Строка 1: / Строка 1: @@
-==Стенина Мария, группа 974==
+Приведите пример графа с отрицательными весами, но без циклов отрицательной длины,
+для которого алгоритм Дейкстры даст неправильный ответ.
-[[Категория:На проверку]]
+<!--Вообще-то, решения уже есть-->
-[[File:Graph.png|thumb|Пример графа]]
+[[Категория:Решенные задачи]]
+[[Категория:Теоретические задачи]]
-Пример графа на рисунке. Есть отрицательные веса. В графе только один цикл длины 1. Если запустить поиск кратчайших путей из первой вершины до всех остальных, то до вершины 2 найдется путь длины 1 (путь 1 -> 2), в то время как есть путь 1 -> 3 -> 4 -> 2 длины 0.