Теория графов

курсовая работа

1. Постановка задачи

Задача. Найти минимальные пути от фиксированной вершины до произвольной вершины графа, используя алгоритм Дейкстры.

Решение задачи будет произведено по алгоритму Дейкстры.

Пусть в орграфе D из вершины v в вершину w, где v w, называется минимальным, если он имеет минимальную длину среди всех путей орграфа D из v в w.

Назовем орграф D = (V,X) нагруженным, если на множестве дуг X определена некоторая функция l : X R, которую часто называют весовой функцией. Значение l(x) будем называть длиной дуги x. Предположим, что l(x) 0. Длиной пути П в нагруженном орграфе будем называть величину l(П), равную сумме длин дуг, входящих в П, при этом каждая дуга учитывается столько раз, сколько она входит в данный путь.

Нагруженный орграф можно задать с помощью матрицы весов С(D) = {cij}nxn с элементами

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

Пусть s - начальная вершина, t - конечная вершина. На каждой итерации любая вершина v имеет метку l*(v), которая может быть постоянной или временной. Постоянная метка l*(v) - это длина кратчайшего пути от s к v, временная метка l(v) - это вес кратчайшего пути из s в v, проходящий через вершины с постоянными метками. Если на каком-то шаге метка становится постоянной, то она остается такой до конца работы алгоритма.

Вторая метка (v) - это вершина, из которой вершина v получила свою метку.

Алгоритм Дейкстры

Данные: матрица весов С(D) орграфа D, начальная вершина s.

Результат: расстояния от вершины s до всех вершин орграфа D: D[v] = d(s,v), v V, а также последовательность вершин, определяющая кратчайший путь из s в v .

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) и (v) =р. Иначе l*(v) и (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, поэтому положим (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, используя метки (v): П = s…(t)t.

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

Делись добром ;)