2.2. Описание программы

Поиск кратчайших путей.

Описание алгоритма:

Над матрицей A (NxN) выполняется n итераций. После k-ой итерации, A[i,j] содержит значение наименьшей длинны путей из вершины i в вершину j, которые не проходят через вершины с номером, большим k.

На k-ой итерации для вычисления матрицы A, используется слудующая формула: Ak[i,j] = min (Ak-1[i,j], Ak-1[i,k]+ Ak-1[k,j]).

Сложность алгоритма

Время выполнения программы, имеетпорядок O(n3), так как в ней нет практически ничего, кроче 3 вложенных друг в друга циклов.

Сохранение маршрутов.

Что бы сохранять маршруты, от одной вершины кдругой, следует, ввести еще одну матрицу, в которой каждому элементу P[I,j]присваивать вершину K (номер), полученную при нахождении наименьшего значения a[I,j].

2.3. Листинг программы

Program Algoritm_Floyda;

Const NN=100; Type Graph = array[1..nn,1..nn] of longint; {граф задан матрицей смежности} Var n:integer; Procedure Floyd (var a:graph; c:graph; var p:graph); var i,j,k:integer; begin for i:=1 to n do for j:=1 to n do begin a[i,j]:=c[i,j]; p[i,j]:=0; end; for i:=1 to n do a[i,i]:=0; for k:=1 to n do for i:=1 to n do for j:=1 to n do If (a[i,k]+a[k,j]<a[i,j]) then begin a[i,j]:=a[i,k]+a[k,j]; p[i,j]:=k; end; end; procedure ReadGraph(var a:graph); var i,j:integer; begin write('n= ');readln(n); For i:=1 to n do for j:=1 to n do begin write('G',i,',',j,'= ');readln(a[i,j]); end; writeln; end; procedure ReadFileGraph(var a:graph); var i,j:integer; filename:string; f:text; begin Write('Enter file name:'); readln(filename); Assign (f,filename); reset(f); Readln(f,N); For i:=1 to n do for j:=1 to n do read(f,a[i,j]); close(f); end; var a,c,p:graph; i,j:integer; begin { ReadGraph( c );} ReadFileGraph( c ); floyd(a,c,p); writeln('---------------------------'); for i:=1 to n do { begin for j:=1 to n do write(a[i,j]:3); writeln end; writeln('---------------------------'); for i:=1 to n do begin for j:=1 to n do write(p[i,j]:3); writeln end; readln; end. В программе C-граф, заданный матрицей смежности. A- матрица содержащая кратчайшие пути. P - матрица, сохраняющая маршруты

Заключение

Графы в большой степени сохраняют своё наглядное, геометрическое содержание как системы точек, соединённых линиями. Ознакомление с новым материалом на основе этих данных не даст им запутаться в незнакомых понятиях и позволит хорошо усвоить и применять на практике полученные знания. Будет способствовать усвоению данного курса и то, что основы теории графов связаны с изучаемыми в средней школе математическими и естественнонаучными предметами. Это даёт возможность, кроме получения новых знаний, глубже и лучше освоить и понять другие предметы школьной программы. Процесс обучения современного человека не заканчивается в школе или вузе. Он становится непрерывным. Системы непрерывного образования – это насущная потребность каждого человека. Поэтому уже в настоящее время возникла необходимость не только в общем обучении, но и в дистанционном, на основе современных компьютерных технологий (как ознакомление с ними, так и непосредственное их использование в решении поставленных задач ). Благодаря наличию дидактических свойств компьютерные телекоммуникации являются исключительно современными и перспективными для использования в сфере образования. В современном интегрированном сообществе учащиеся уже не могут учиться изолированно, ограничиваясь традиционными, достаточно замкнутым социумом: учителя, друзья, семья.

Список литературы

1. Белов Теория Графов, Москва, «Наука»,1968.

2. Новые педагогические и информационные технологии Е.С.Полат, Москва, «Akademia» 1999 г.

3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988.

4. Кук Д., Бейз Г. Компьютерная математика. – М.: Наука, 1990.

5. Нефедов В.Н., Осипова В.А. Курс дискретной математики. – М.: Издательство МАИ, 1992.

6. Лекции по теории графов. / Емеличев В.А., Мельников О.И. и др. М.: Наука, 1990.

7. http://www.vbstreets.ru/default.asp?page=library&type=old&id=volna

8. http://www.devel.vcity.ru/library.tmpl?05344_article_id=8

9. http://www.wikipedia.ru/theory/

10. http://www.algolist.manual.ru/links/

11. http://www.caravan.ru/~alexch/graphs

12. http://www.encycl.yandex.ru/