Скачать Минимизация на графе по алгоритму Дейкстры

07.12.1995
Скачать файл (21,04 Кб)

Программа выполняет минимизацию на графе при помощи алгоритма Дейкстры.

Алгоритм Дейкстры строит кратчайшие пути,ведущие из исходной вершины графа к остальным вершинам этого графа./Если,конечно,таковые имеются.../
В процессе работы алгоритма последовательно помечаються достижимые вершины графа.Причем вершина,помеченная последней /на данный момент/ расположена ближе к исходной вершине,чем все непомеченные,но дальше,чем все помеченные.
Сначала помечается исходная вершина;Следующей,очевидно,будет помечена верши- на,ближайшая к исходной,и смежная с ней.
Пусть на каком-то шаге уже помечено несколько вершин.Известны кратчайшие пути ,ведущие из исходной вершины к помеченным.Для каждой из непомеченных вершин про- делаем следующее: Рассмотрим все дуги,ведущие из помеченных вершин в одну непо- меченную.Каждая такая дуга является последней дугой на пути из исходной вершины в эту непомеченную.Выберем из этих путей кратчайший.А из этих кратчайших путей ко всем непомеченным вершинам выберем наикратчайший,и пометим вершину,к которой он ведет.
Алгоритм завершится,когда будут помечены все достижимые вершины.
В результате работы алгорима Дейкстры строится Дерево Кратчайших Путей.

/Материал взят из книги 'Решение задач с помощью стандартных подпрограмм' - А.М.Ветошкин,А.В.Корольков,А.И.Батарин,Т.А.Крылова./,/p>

Типы.

В программе используются следующие типы данных:

   Тип граф:
     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;                      - Ука