Граф со взвешенными дугами

Граф G = (N, A) называется взвешенным, если на множестве дуг A определена некоторая функция l: A → R, которую называют весовой функцией.

Тем самым в взвешенном графе G каждой дуги x A поставлено в соответствие некоторое действительное число l(x). Значение l(x) называются длиной дуги x.

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

Путь в взвешенном графе G из вершины V в вершину щ, где V ≠ щ, называется минимальным, если он имеет минимальную длину среди всех путей графа G.

Пример. Рассмотрим задачу поиска минимальных путей в взвешенном графа. Это задача и о кратчайшем соединении:

Даны населенные пункты v₁, v₂, v₃, v₄, v₅, v₆, известны трассы дорог, соединяющие эти пункты, и длина трасс (в км). Требуется определить минимальный путь из пункта v₁ в пункт v₆. Все данные приведены на рис.

Решение

Дан взвешенный граф G=(N, A), где N={v₁, v₂,..., v₆}. Для нахождения минимального пути будем использовать алгоритм Форда-Беллмана.

Вначале введем ряд определений.

Введем величину l_i^(k), где i = 1...6, k = 1, 2...

Для каждых фиксированных i и k величина l_i^(k) равна длине минимального пути среди путей из v₁ в v_i, содержащих не более k дуг; если же таких путей нет, то l_i^(k) = ∞. Кроме того, если произвольную вершину v_i, i = 1...6 считать путем из v₁ в v_i нулевой длины, то величины l_i^(k) можно ввести также и для k = 0, при этом l_i⁽⁰⁾ = , l_i⁽⁰⁾ = ∞, i=2... 6.

Введем также в рассмотрение квадратную матрицу C(G) = [C_ij] порядка n = 2 … 6 с элементами C_ij =

Дата добавления: 2015-07-07