Алгоритм вычисления стоимости прохождения между узлами

Алгоритм вычисления стоимости прохождения между узлами

Вход. Орграф G = (V, E), где V = {v₁, …, v_n}, l – функция разметки такая, что l: (V ´ V) ®S, где  (S, +, ·, 0, 1) – замкнутое полукольцо. Полагаем, l(v_i, v_j) = 0, если (v_i, v_j) Ï E.

Выход. Для любых i и  j, изменяющихся в диапазоне от 1 до n найти элемент c(v_i, v_j) Î S. Это сумма по всем путям из v_i, в v_j  меток этих путей.

Ещё посмотрите лекцию "45. Выбор безопасных систем отопления" по этой теме.

Метод. Вычисляем

 Эта величина равна сумме меток путей, идущих из v_i, в v_j, все узлы которых, кроме, может быть, концевых, принадлежат множеству {v₁, v₂, …, v_k}. Например, путь v₉, v₃, v₈ рассматривается при вычислении , но не рассматривается при вычислении .

Таким образом, это сумма меток всех путей из v_i, в v_j, не содержащих промежуточных узлов с индексами больше k.

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