Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

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

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

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

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

 

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

Даны населенные пункты v1, v2, v3, v4, v5, v6, известны трассы дорог, соединяющие эти пункты, и длина трасс (в км). Требуется определить минимальный путь из пункта v1 в пункт v6. Все данные приведены на рис.

Решение

 

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

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

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

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

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


Дата добавления: 2015-07-07; просмотров: 131 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Обратное соответствие| Алгоритм Форда-Беллмана

mybiblioteka.su - 2015-2021 год. (0.009 сек.)