Поиск кратчайших путей в планарных графах с отрицательными весами ребер: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) м (→Нотация) |
Irina (обсуждение | вклад) м (→Применение) |
||
Строка 77: | Строка 77: | ||
== Применение == | == Применение == | ||
Задача поиска кратчайших путей давно | Задача поиска кратчайших путей давно стала предметом изучения, она находит применение в самых разных областях. Существует множество задач, сводимых к задаче поиска кратчайших путей, в которых предполагаются отрицательные веса ребер; в качестве примера можно привести поиск ориентированной схемы с минимальной средней длиной. Для планарных графов данная задача широко применяется даже в случаях, когда лежащий в основе задачи граф представляет собой решетку. Например, недавно разработанные подходы к сегментации изображений используют функцию определения отрицательных циклов [2, 3]. В числе других областей применения планарных графов можно упомянуть алгоритмы поиска сепараторов [13] и алгоритмы потока с несколькими источниками и несколькими стоками [13]. | ||
== Открытые вопросы == | == Открытые вопросы == |