4551
правка
Отрицательные циклы во взвешенных орграфах: различия между версиями
Материал из WEGA
Отрицательные циклы во взвешенных орграфах (посмотреть исходный код)
Версия от 13:20, 17 января 2016
, 17 января 2016→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
Задача нахождения отрицательного цикла тесно связана с задачей нахождения кратчайшего пути. В последней необходимо найти путь с минимальной стоимостью между двумя вершинами s и t. Легко увидеть, что кратчайший путь s-t существует в том и только том случае, если ни один путь s-t в графе G не содержит отрицательного цикла [1 , 13]. Также известно, что все кратчайшие пути от заданной вершины s до всех других вершин формируют дерево, называемое [[дерево кратчайших путей|деревом кратчайших путей]] [1, 13]. | Задача нахождения отрицательного цикла тесно связана с задачей нахождения кратчайшего пути. В последней необходимо найти путь с минимальной стоимостью между двумя вершинами s и t. Легко увидеть, что кратчайший путь s-t существует в том и только том случае, если ни один путь s-t в графе G не содержит отрицательного цикла [1, 13]. Также известно, что все кратчайшие пути от заданной вершины s до всех других вершин формируют дерево, называемое [[дерево кратчайших путей|деревом кратчайших путей]] [1, 13]. | ||
== Основные результаты == | == Основные результаты == | ||
