Автор работы: Пользователь скрыл имя, 11 Ноября 2014 в 15:22, курсовая работа
Алгоритм Флойда находит кратчайшие пути между всеми парами вершин в орграфе. В этом алгоритме для хранения информации о путях используется матрица H[1..р, 1..р], где
Матрица Н размера 0(р2) хранит информацию обо всех (кратчайших) путях в графе. Заметим, что всего в графе 0(р2) путей, состоящих из 0(р) вершин.
Глава 1. Основные понятия и определения теории графов
1.1 Методы нахождения кратчайших путей в графе……..3
1.3. Алгоритм Флойда Уоршалла…………………….……8
1.4. Листинг программы……………………………….......11
1.5. Примеры применения программы……………………12
Литература…………………………………………………………...13
Нижегородский государственный технический
универсИтет
Заволжский филиал
КУРСОВОЙ ПРОЕКТ
по учебной дисциплине
«Информатика и компьютерные технологии»
НА ТЕМУ:
Автоматизация алгоритма Флойда Уоршалла
студента группы 13-ИВТ
Рябова Антона
Руководитель по курсовому проекту:
Отчет по курсовому проекту принял: : Ястребов И.П.
г. Заволжье
2014
Содержание
Глава 1. Основные понятия и определения теории графов
1.1 Методы нахождения кратчайших путей в графе……..3
1.3. Алгоритм Флойда Уоршалла…………………….……8
1.4. Листинг программы……………………………….......11
1.5. Примеры применения программы……………………12
Литература……………………………………………………
Теория графов – дисциплина математическая, созданная усилиями математиков, поэтому ее изложение включает в себя и необходимые строгие определения. Итак, приступим к организованному введению основных понятий этой теории.
Начальные понятия
Будем рассматривать ориентированные графы G =(V,E) , дугам которых приписаны веса. Это означает, что каждой дуге E поставлено в соответствие некоторое вещественное число a (u, v), называемое весом данной дуги.
Нас будет интересовать нахождение кратчайшего пути между фиксированными вершинами s, t ?V. Длину такого кратчайшего пути мы будем обозначать d (s, t) и называть расстоянием от s до t (расстояние, определенное таким образом, может быть отрицательным). Если не существует ни одного пути из s в t, то полагаем d (s, t) = + . Если каждый контур нашего графа имеет положительную длину, то кратчайший путь будет всегда элементарным путем, т.е. в последовательности v1,..., vp не будет повторов.
С другой стороны, если в графе существует контур отрицательной длины, то расстояние между некоторыми парами вершин становится неопределенным, потому что, обходя этот контур достаточное число раз, мы можем показать путь между этими вершинами с длиной, меньшей произвольного вещественного числа. В таком случае, можно было бы говорить о длине кратчайшего элементарного пути, однако задача, поставленная таким образом, вероятно будет значительно более сложной, так как, в частности, она содержит в себе задачу существования гамильтонова пути.
Сначала рассмотрим алгоритмы нахождения расстояния между вершинами, а не самих путей. Однако, зная расстояние, мы можем при условии положительной длины всех контуров легко определить кратчайшие пути. Для этого достаточно отметить, что для произвольных s, t ? V (s , t) существует вершина v, такая что d (s, t) = d (s, v) + a (v, t).
Действительно, таким свойством обладает предпоследняя вершина произвольного кратчайшего пути из s в t.
Далее мы можем найти вершину u, для которой d (s, v) = d (s, u) + a(u, v), и т.д.
Из положительности длины всех контуров легко следует, что созданная таким образом последовательность t, v, u, ... не содержит повторений и оканчивается вершиной s. Очевидно, что она определяет (при обращении очередности) кратчайший путь из s в t.
Способы задания графа
Рассмотрим различные способы задания для одного и того же графа.
1. < {а, Ь, с, d), {и, v, w,x); {(и, а),(и, b),(v, b),(v,
c),(w, c),(w, a),(x, с), (x, d)} >. Так как
мы рассматриваем только простые графы,
граф нам проще определять как модель,
носителем которой является множество
вершин, а отношение - бинарное отношение
смежности вершин. Тогда данный граф запишется как<{а,Ь,с,с1}; {(a,b),
(b,a),(b,c),(c,b),(a,c),(c,a),
В дальнейшем мы будем опираться именно на второе определение графа.
2. Геометрический
3. Матрица смежности
а |
b |
с |
d | |
а |
0 |
1 |
1 |
0 |
b |
1 |
0 |
1 |
0 |
с |
1 |
1 |
0 |
1 |
d |
0 |
0 |
1 |
0 |
4. Матрица инцидентности
u |
V |
w |
X | |
а |
1 |
0 |
0 |
0 |
b |
1 |
1 |
1 |
0 |
с |
0 |
1 |
0 |
1 |
d |
0 |
0 |
1 |
1 |
Алгоритм Флойда находит кратчайшие пути между всеми парами вершин в орграфе. В этом алгоритме для хранения информации о путях используется матрица H[1..р, 1..р], где
ОТСТУПЛЕНИЕ
Матрица Н размера 0(р2) хранит информацию обо всех (кратчайших) путях в графе. Заметим, что всего в графе 0(р2) путей, состоящих из 0(р) вершин. Таким образом, непосредственное представление всех путей потребовало бы памяти объема 0(р3). Экономия памяти достигается за счет интерпретации представления, то есть динамического вычисления некоторой части информации вместо ее хранения в памяти. В данном случае любой конкретный путь (u>v) легко извлекается из матрицы с помощью следующего алгоритма.
ЗАМЕЧАНИЕ
Если в G есть цикл с отрицательным весом, то решения поставленной задачи не существует, так как можно "накручивать" на этом цикле сколь угодно короткий путь.
Обоснование
Алгоритм Флойда имеет много общего с алгоритмом Уоршалла (алгоритм 1.8). Покажем по индукции, что после выполнения i-го шага основного цикла по I элементы матриц T[j,k] и H[j, k] содержат, соответственно, длину кратчайшего пути и первую вершину на кратчайшем пути из вершины j в вершину к, проходящем через промежуточные вершины из диапазона 1..i. База: i = 0, то есть до начала цикла элементы матриц Т и H содержат информацию о кратчайших путях (если таковые есть), не проходящих ни через какие промежуточные вершины. Пусть теперь перед началом выполнения тела цикла на i-м шаге T(j, k) содержит длину кратчайшего пути от j к k , a H\j> к) содержит первую вершину на кратчайшем пути из вершины j в вершину к (если таковой есть). В таком случае, если в результате добавления вершины г к диапазону промежуточных вершин находится более короткий путь (в частности, если это вообще первый найденный путь), то он записывается. Таким образом, после окончания цикла, когда i = p матрицы содержат кратчайшие пути, проходящие через промежуточные вершины 1..р, то есть искомые кратчайшие пути. Алгоритм не всегда выдает решение, поскольку оно не всегда существует. Дополнительный цикл по j служит для прекращения работы в случае обнаружения в графе цикла с отрицательным весом.
«Примечание бесконечность вводить как отрицательное число»
var A:array [ 1..20, 1..20] of real;
B:array [ 1..20, 1..20] of real;
i, j, k, z, h, n : integer;
t : real;
BEGIN
{Заполняем массив числами}
writeln('введите количество вершин ');
read(n);
writeln('введите эллементы матрицы в строчку');
for j := 1 to N do begin
for i := 1 to N do begin
read(A [ i,j])
end;
writeln;
end;
for i := 1 to N do begin
for j := 1 to N do begin
if a[i,j]<0 then
a[i,j]:=100000000000
end;
end;
for i := 1 to N do begin
for j := 1 to N do begin
b[i,j]:=a[i,j]
end;
end;
for i := 1 to N do begin
for j := 1 to N do begin
if b[i,j]>0 then
begin
t:=b[i,j];
for h:=1 to n do begin
a[h,i]:=a[h,i]+t;
if a[h,i]<b[h,j] then
b[h,j]:=a[h,i]
end;
end;
for k := 1 to N do begin
for z := 1 to N do begin
a[k,z]:=b[k,z]
end;
end;
end;
end;
for i := 1 to N do begin
for j := 1 to N do begin
if a[i,j]=100000000000 then
a[i,j]:=-1
end;
end;
for j := 1 to N do begin
for i := 1 to N do begin
write(a [ i,j]:4)
end;
writeln;
end;end.
алгоритм
6. Литература
Размещено на Allbest.ru