Нагруженный граф. Пути в графе. Нахождение минимального пути в графах

Нагруженный граф – орграф G = (V, X), для которого задана функция ставящая в соответствие каждой дуге этого графа некоторое вещественное число – длина (вес) дуги x l(x). Можно задать с помощью матрицы весов:

Путь, соединяющий вершины v₁ и v_k в орграфе G– последовательность v₁, x₁, v₂, x₂, …, v_k-1, x_k-1, v_k, где v_i – вершина, x_i=(v_i,v_i+1).

Замкнутый путь – путь (маршрут), у которого первая и последняя вершины совпадают. Замкнутый путь, который проходит через каждую дугу (ребро) только 1 раз называется циклом. Цикл, который проходит через каждую вершину 1 раз называется простым.

Цепь – незамкнутый путь (маршрут), который проходит через каждую дугу(ребро) только 1 раз. Цепь, которая проходит через каждую вершину 1 раз называется простой.

Длина пути (для ненагруженного графа) – количество дуг, входящих в этот путь.

Длина пути (для нагруженного графа) – сумма весов дуг, входящих в этот путь. Минимальный путь [между вершинами v₁ и v_k] – путь, имеющий минимальную длину среди всех других путей [из v₁ в v_k].

Алгоритм Дейкстры (поисл min пути в нагруженном графе)

1. Положим l*(s) = 0 и будем считать эту метку постоянной. Для всех v ОV, v № s, положим l*(v) = Ґ и будем считать эти метки временными. Положим p = s.

2. Для всех vОГp с временными метками выполним: если l*(v)>l*(p)+l(p,v), то l*(v)=l*(p)+l(p,v) и Q(v) =р. Иначе l*(v) и Q(v) не менять, т.е. l*(v) = min (l*(t), l*(p)+cpv). (Идея состоит в следующем: пусть p – вершина, получившая постоянную метку l*(p) на предыдущей итерации. Просматриваем все вершины vОГp, имеющие временные метки. Метка l*(v) вершины vОГp заменяется на l*(p)+l(p,v), если оказывается, что ее метка l*(v)>l*(p)+l(p,v). В этом случае говорим, что вершина v получила свою метку из вершины p, поэтому положим Q(v) = p. С помощью этих дополнительных меток будем потом восстанавливать сам путь. Если l*(v) Ј l*(p)+cpv, то метки остаются прежними.

3. Пусть V* - множество вершин с временными метками. Найдем вершину v* такую, что l*(v*) = min l*(v), v О V*. Считать метку l*(v*) постоянной для вершины v*.

4. Положим p = v*. Если p = t, то перейдем к п.5 (l*(t) – длина минимального пути). Иначе перейдем к п.2.

5. Найдем минимальный путь из s в t, используя метки Q(v): П = s…Q(t)t.