Несложно о сложности. Примеры алгоритмов/Задачи/ex-dijksta-not-work-on-negative-weight — различия между версиями
Материал из DISCOPAL
(→Стенина Мария, группа 974) |
(→Стенина Мария, группа 974) |
||
Строка 5: | Строка 5: | ||
[[File:Graph.png|thumb|Пример графа]] | [[File:Graph.png|thumb|Пример графа]] | ||
+ | |||
+ | Пример графа на рисунке. Есть отрицательные веса. В графе только один цикл длины 1. Если запустить поиск кратчайших путей из первой вершины до всех остальных, то до вершины 2 найдется путь длины 1 (путь 1 -> 2), в то время как есть путь 1 -> 3 -> 4 -> 2 длины 0. |
Версия 10:02, 12 сентября 2014
Стенина Мария, группа 974
Пример графа на рисунке. Есть отрицательные веса. В графе только один цикл длины 1. Если запустить поиск кратчайших путей из первой вершины до всех остальных, то до вершины 2 найдется путь длины 1 (путь 1 -> 2), в то время как есть путь 1 -> 3 -> 4 -> 2 длины 0.