Каково значение отрицательных весовых граней на графике?

Я делал упражнения по динамическому программированию и нашел алгоритм Флойда-Варшалла. По-видимому, он находит кратчайшие пути из всех пар для графа, который может иметь отрицательные весовые ребра, но без отрицательных циклов.

Итак, мне интересно, каково в действительности значение отрицательных краев веса? Простое английское объяснение было бы полезно.

Саид Амири уже привел отличный пример в комментарии: вес по краям может представлять что угодно в реальном мире, например, сумму денег, которая будет переведена с одного счета на другой. Суммы могут быть положительными или отрицательными. Например, если вы хотите перейти от к b на своем графике, потеряв при этом как можно меньше денег (кратчайший путь), вы можете рассмотреть отрицательные веса. Для получения дополнительной информации см. Эту главу книги .$a$$b$

Помимо этого, есть еще много приложений. Отрицательные веса зависят от того, что вы имитируете. Например, рассмотрим этот график

• $e_{uv}$$v$$u$$4$$s-a$$2$$a$$t$$5$$s$$t$

• $s$$t$$a$$b$

• $b$$s$$a$$a$$t$$t$$s$

Я не специалист по химии, но все же я думаю, что этот пример будет полезен, чтобы помочь вам продумать процессор, теорию сетей и тому подобное ..

Рассмотрим график, имитирующий поведение молекулы в химической реакции, т. Е. Какие пути он может пройти во время реакции, а весовые коэффициенты представляют собой энергию, поглощенную или выделенную при переходе, поэтому, если мы хотим получить энергию из реакции, мы представляем выделенную энергию с + ve весами и поглощенными энергия с -ве.

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

Проблема возникает, когда есть отрицательный цикл. Посмотрите на график выше. И задайте себе вопрос - каков кратчайший путь между А и Е? Сначала вы можете почувствовать, что его ABCE стоит 6 (2 + 1 + 3). Но на самом деле, если взглянуть глубже, вы увидите отрицательный цикл, который является BCD. Вес BCD составляет 1 + (- 4) +2 = (-1). Переходя от A к E, я мог бы продолжать ездить внутри BCD, чтобы каждый раз снижать свои затраты на 1. Мол, путь A (BCD) BCE стоит 5 (2 + (- 1) + 1 + 3). Теперь повторение цикла бесконечное число раз будет уменьшать стоимость на 1 каждый раз. Я мог бы достичь отрицательного бесконечного кратчайшего пути между А и Е.

Проблема очевидна для любого отрицательного цикла в графе. Следовательно, всякий раз, когда присутствует отрицательный цикл, минимальный вес не определен или является отрицательной бесконечностью, поэтому Флойд-Варшалл не может работать в таком случае.

Кроме того, вы можете взглянуть на алгоритм Беллмана-Форда, который определяет, имеет ли граф отрицательный цикл или нет, и в противном случае возвращает кратчайший путь между двумя узлами.

Например, представьте логистическую сеть, в которой вес w (i, j) ребра ij - это стоимость перехода от вершины i к вершине j. Если вы заключили деловое соглашение с другими компаниями на транспортировку их продуктов, то w (i, j) будет прибылью, а не затратами, поэтому вы можете интерпретировать этот вес как отрицательную стоимость.

Пробки на карте:

Другим реальным примером привязки весов к краю может быть вес, представляющий условия движения на карте (более отрицательный, более неблагоприятный) - тогда мы могли бы использовать это представление для вычисления оптимальных расстояний.

Мы действительно можем использовать метафору «вес» для представления чего-либо положительного / отрицательного значения между любыми двумя точками на графике