Отрицательные веса

Теперь обратимся к теме, связанной с отрицательными весами в задачах поиска крат­чайших путей. Возможно, отрицательные веса ребер покажутся неестественными, по­скольку на протяжении большей части этой главы мы на интуитивных примерах привык­ли, что веса представляют расстояния или стоимости. Однако, как было показано в разделе 21.6, отрицательные веса ребер возникают естественным путем, когда к задаче поиска кратчайших путей сводятся другие задачи. Отрицательные веса являются не толь­ко математической абстракцией; напротив, они существенно расширяют применимость задач кратчайших путей в качестве модели для решения других задач. Эта потенциальная польза побуждает нас искать эффективные алгоритмы для решения сетевых задач, допус­кающих наличие отрицательных весов.

Глава 21, Кратчайшие пути

РИСУНОК 21.26. ТИПОВАЯ СЕТЬ С ОТРИЦАТЕЛЬНЫМИ РЕБРАМИ

Это та же типовая сеть, что и сеть, показанная на рис. 21.1, за исключением того, что ребра 3-5 и 5-1 являются отрицательными. Естественно, данное изменение существенным образом воздействует на структуру кратчайших путей, что легко заметить путем сравнения матриц расстояний и путей справа с соответствующими матрицами на рис. 21.9. Например, кратчайший путь из 0 в 1 в этой сети есть 0-5-1, и он имеет длину 0, тогда как кратчайший путь из 2 в 1 есть 2-3-5-1 с длиной -0.17.

Рисунок 21.26 представляет небольшой пример, который иллюстрирует влияние вве­дения отрицательных весов в задаче о наиболее коротких путях в сети. Возможно, при этом наиболее важный эффект состоит в том, что когда присутствуют отрицательные веса, то наиболее короткие пути с малыми весами имеют тенденцию содержать больше ребер, чем пути с более высокими весами. В случае положительных весов нашей целью было искать кратчайшие расстояния; однако, при наличии отрицательных весов мы ищем обходные пути (detours), которые используют столько ребер с отрицательными весами, сколько мы сможем отыскать. Этот эффект производит переворот в нашем интуитивном понимании поиска алгоритмов " коротких" путей, так что нам потребуется преодолеть этот барьер интуиции и рассмотреть данную задачу на базовом абстрактном уровне.

Отношение между кратчайшими путями в сетях и гамильтоновыми путями в графах, показанное при доказательстве свойства 21.18, связано с нашим наблюдением, что поиск путей низкого веса (которые мы называем " короткими") равноценен поиску путей с боль­шим количеством ребер (которые мы могли бы считать " длинными"). При наличии отри­цательных весов мы ищем скорее длинные пути, нежели короткие.

Первая мысль, которая приходит на ум, дабы исправить ситуацию, — это найти наи­меньший (наиболее отрицательный) вес ребра, затем добавить абсолютное значение это­го числа ко всем весам ребер, чтобы превратить сеть в такую, которая не имеет отрица­тельных весов. Это наивное приближение вообще не работает из-за того, что кратчайшие пути в новой сети не имеют никакого отношения к кратчайшим путям в прежних сетях. Например, в сети приведенной на рис. 21.26, кратчайший путь из 4 в 2 есть 4-3-5-1-2. Если увеличить на 0.38 веса всех ребер в графе, чтобы сделать их все положительными, вес этого пути возрастет от 0.20 до 1.74. Однако вес 4-2 возрастет в действительности с 0.32 до 0.70, так что это ребро станет кратчайшим путем из 4 в 2. Чем больше ребер име­ет путь, тем больше он страдает от такого преобразования, поэтому результат, по срав­нению с тем, что мы наблюдали в предыдущем параграфе, как раз противоположен тому, что требуется. Даже если эта наивная идея не работает, цель преобразования сети в эк­вивалентную, без отрицательных весов, но с теми же кратчайшими путями, вполне дос­тойна внимания; в конце раздела мы рассмотрим алгоритм достижения упомянутой цели.