Читать реферат по всему другому: "работа по курсу «Дискретная математика» Тема: Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов" Страница 1

(Назад) (Cкачать работу)

Тема: Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов

Вариант №22

Содержание курсовой работы

Пояснительная записка к курсовой работе должна содержать следующие разделы:

постановка задачи;теоретическая часть;описание алгоритма решения поставленной задачи;ручной просчет (на небольшом примере показать работу алгоритма);описание программы;тесты;список использованной литературы;листинг программы.

ЗАДАНИЯ К КУРСОВОЙ РАБОТЕ

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

Путь в орграфе 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 с элементами

l(vi,vj), если (vi,vj) X,

cij =

,если (vi,vj) X.

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

Пусть 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 .

Положим l*(s) = 0 и будем считать эту метку постоянной. Для всех v V, v  s, положим l*(v) =  и будем считать эти метки временными. Положим p = s. Для всех 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, то метки остаются прежними.

Пусть V* - множество вершин с временными метками. Найдем вершину v* такую, что

Похожие работы