Введение в теорию графов. Алгоритмы на графах



Скачать 24.18 Kb.
Дата04.07.2013
Размер24.18 Kb.
ТипГлава


155


154

Глава 6. Введение в теорию графов. Алгоритмы на графах

6.9. Кратчайшие пути на графе

Алгоритм 6.12. Программа кратчайшего пути на орграфе

Program Short; {Кратчайшие пути на графе)

uses CRT,DOS;

Const

nVertex=50; {Максимальное количество вершин}

Type

TypeMark=array[0..nVertex] of Boolean; TypeDist=array[0..nVertex] of Longlnt; TypePrev=array[0..nVertex] of Integer; TypeWeight=array[0..nVertex,0..nVertex] of Integer;

Var

f :Text; { Текстовый файл }

nX :Integer; { Количество вершин в графе }

Mark :TypeMark; (Признаки временных и постоянных меток}

Dist :TypeDist; { Значения текущих меток вершин

(расстояния)}

Prev rTypePrev; { Указатель на ближайшую вершину } We :TypeWeight; { Матрица весов ребер графа } хО :Integer; { Вершина начала пути } z :Integer; { Вершина конца пути } у :Integer; (Последняя вершина с постоянной меткой}

Var

i,j,x :Integer; weight :Longlnt; begin

Assign(f,'Short.in');

Reset(f);(Файл открыт для чтения}

{Ввод исходных данных]

Read(f,xO); (Начальная вершина пути}

Read(f,z); (Конечная вершина пути}

Read(f,nX); (Количество вершин в графе}

пХ:=пХ-1; (* Х={О,1,2,...,пХ} - множество вершин *)

for i:=0 to nX do begin

for j:=0 to nX do begin

Read(f,We[i,j]); ( Ввод матрицы весов }

if We[i,j]=0 then We [i, j ] :=$7f f f; {-f бесконечность }

end; end;

Close(f);

Assign(ft ' Short.out'); Rewrite(f); (Файл открыт для записи}

for x:=0 to nX do begin

Mark[x]:=FALSE; Distfx]:=$7fffffff; end;

у:=хО; {Последняя вершина с постоянной меткой} Mark[у]:=TRUE; Dist[у]:=0;

while not Mark[z] do begin

{Обновить временные метки]

for x:=0 to nX do if not Mark[x] and

( Dist[x]>Dist[y]+We[y,x] ) then begin Dist[x]:=Dist[y]+We[y,x]; Prev[x]:=y; end;

(Поиск вершины с минимальной временной меткой] weight:=$7fffffff;

for x:=0 to nX do if not Mark[x] then if weight>Dist[x] then begin weight:=Dist[x]; y:=x; end;

Mark[y]:=TRUE; end;

Write(f,'Вершины пути='); x:=z;

while x<>xO do begin Write(f,x:2); x:=Prev[x]; end;

WriteLn(f,x:2);

WriteLn(f,'Длина пути= \Dist[z]); Close(f); end.

Рассмотрим пример расчета по программе алгоритма 6.12 по­иска кратчайшего пути на графе, показанном на рис. 6.21.
Исход­ные данные графа представляются матрицей весов его ребер в текстовом файле Short.in со следующей структурой:


в первой строке определяется номер начальной вершины пути х$\

во второй строке определяется номер конечной вершины пути z;

в третьей строке указывается количество пХ вершин в графе;

в следующих «^строках определяются строки матрицы весов [w^] графа.

Похожие:

Введение в теорию графов. Алгоритмы на графах iconРабочая программа дисциплины Графы и алгоритмы Направление подготовки Профиль подготовки Квалификация (степень) выпускника
Охватывает круг вопросов, связанных с основами современной теории графов, классическими алгоритмами на графах, спецификой их применения,...
Введение в теорию графов. Алгоритмы на графах iconЛабораторная работа «представление графов. Алгоритмы на графах»
Изучить способы представления графов с помощью матриц: матрица смежностей, матрица инцидентности, матрица достижимости, другие матричные...
Введение в теорию графов. Алгоритмы на графах iconАлгоритмы на графах. Обходы графов. Кратчайшие пути. Остовные деревья
Ориентированный граф (сокращенно орграф) g = (V, E) состоит из множества вершин V и множества дуг E. Вершины также называют узлами,...
Введение в теорию графов. Алгоритмы на графах iconМетодические указания по проведению лабораторных работ «Задачи декомпозиции графов»
Вых структурах. Дается содержательное описание объекта исследования, строится общая математическая модель, ставятся оптимизационные...
Введение в теорию графов. Алгоритмы на графах iconПрограмма дисциплины «теория графов»
Таким образом, теория графов стала существенной частью математического аппарата кибернетики, языком дискретной математики. В значительной...
Введение в теорию графов. Алгоритмы на графах iconВведение в теорию
Кашкин В. Б. Введение в теорию коммуникации: Учеб пособие. Воронеж: Изд-во вгту, 2000. 175 с
Введение в теорию графов. Алгоритмы на графах iconЭкзаменационные вопросы интернет-курсов интуит (intuit) : Введение в теорию графов
В алгоритме Дейкстра зависит ли число число итераций для нахождения кратчайших путей до всех вершин графа, состоящего из n вершин,...
Введение в теорию графов. Алгоритмы на графах iconПрограмма дисциплины «Введение в теорию коммуникации»
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов специальности 030501. 65 «Юриспруденция»...
Введение в теорию графов. Алгоритмы на графах iconНеизбыточные алгоритмы обхода ориентированных графов. Недетерминированнный случай
Данная статья является продолжением статьи [18], которая была посвящена обходу детерминированных графов как основе тестирования конечных...
Введение в теорию графов. Алгоритмы на графах iconТеория графов и ее приложения
Основные понятия. Графы неориентированные и ориентированные. Способы задания графов. Матрицы смежности и инцидентности графа. Понятие...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org