Информационный сервер для программистов: Исходники со всего света. Паскальные исходники со всего света
  Powered by Поисковый сервер Яndex: Найдется ВСЁ!
На Главную Исходники Форум Информер Страны мира
   Математика    >>    minygraf
   
 
 Минимизация на графе по алгоритму Дейкстры  Сергей Мирончев 07.12.1995

Пpограмма ищет кpатчайшие пyти на гpафе



20k 
 

Hello All! По многочисленным пpосьбам тpyдящихся кидаю сие твоpение пpям сюды. Hапоминаю пpога ищет кpатчайшие пyти на гpафе. {> Cut here. FileName= MINYGRAF.DOC } Курсовая работа. Программа выполняет минимизацию на графе при помощи алгоритма Дейкстры. Алгоритм Дейкстры строит кратчайшие пути,ведущие из исходной вершины графа к остальным вершинам этого графа./Если,конечно,таковые имеются.../ В процессе работы алгоритма последовательно помечаються достижимые вершины графа.Причем вершина,помеченная последней /на данный момент/ расположена ближе к исходной вершине,чем все непомеченные,но дальше,чем все помеченные. Сначала помечается исходная вершина;Следующей,очевидно,будет помечена верши- на,ближайшая к исходной,и смежная с ней. Пусть на каком-то шаге уже помечено несколько вершин.Известны кратчайшие пути ,ведущие из исходной вершины к помеченным.Для каждой из непомеченных вершин про- делаем следующее: Рассмотрим все дуги,ведущие из помеченных вершин в одну непо- меченную.Каждая такая дуга является последней дугой на пути из исходной вершины в эту непомеченную.Выберем из этих путей кратчайший.А из этих кратчайших путей ко всем непомеченным вершинам выберем наикратчайший,и пометим вершину,к которой он ведет. Алгоритм завершится,когда будут помечены все достижимые вершины. В результате работы алгорима Дейкстры строится Дерево Кратчайших Путей. /Материал взят из книги 'Решение задач с помощью стандартных подпрограмм' - А.М.Ветошкин,А.В.Корольков,А.И.Батарин,Т.А.Крылова./ Типы. В программе используются следующие типы данных: Тип граф: GrafType=record ListVertex:VertexPtr; - Указатель на список вершин. VertNumber:Byte; - Количество вершин. UserWeight:Boolean; - Признак пользовательского веса дуг. end; Тип вершина: VertexPtr=^Vertex; - Указатель на вершину. Vertex=record Vert:Byte; - Номер вершины. ListArc:ArcPtr; - Список дуг,идущих от этой вершины. NextVertex:VertexPtr; - Указатель на следующую вершину. Mark:Boolean; - Флаг 'помеченности'. X,Y:Integer; - Координаты на экране. end; Тип дуга: ArcPtr=^Arc; - Ука