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

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

Версия 00:05, 26 декабря 2014

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