Поиск кратчайших путей в планарных графах с отрицательными весами ребер: различия между версиями

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