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

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

Версия 15:49, 20 мая 2020

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

Источник — «https://discopal.ispras.ru/index.php?title=Несложно_о_сложности._Примеры_алгоритмов/Задачи/ex-dijksta-not-work-on-negative-weight&oldid=11061»