Алгоритм Дейкстры

            Си ++ обеспечивает полный набор операторов структурного программирования. Он также предлагает необычно большой набор операций. Многие операции Си ++ соответствуют машинным командам, и поэтому допускают прямую трансляцию в машинный код. Разнообразие операций позволяет выбирать их различные наборы для минимизации результирующего поля.

            Си ++ поддерживает указатели  не переменные и функции. Указатель на объект программы соответствует  машинному адресу этого объекта. Посредством разумного использования указателей можно создавать эффективно-выполняемые программы, так как указатели позволяют ссылаться на объекты тем же самым путём, как  это делает машина. Си ++ поддерживает арифметику указателей, и тем самым  позволяет осуществлять непосредственный  доступ и манипуляции с адресами памяти.

            В своём составе Си ++ содержит препроцессор, который  обрабатывает текстовые файлы перед компиляцией. Среди его наиболее полезных приложений при написании программ на Си ++ являются: определение программных констант, замена вызова функций аналогичными, но более быстрыми макросами, условная компиляция. Препроцессор не ограничен процессированием только исходных  текстовых файлов Си ++, он может быть использован для любого текстового файла.

       Си ++ - гибкий язык, позволяющий принимать в конкретных ситуациях самые разные решения.

Исходя  из вышеизложенного для написания  программы, был выбран язык программирования Borland С ++ Builder версии 6.0, стандарта ISO/IEC 144882. 

            2.3 Разработка программы. 

            Основываясь на разработанном алгоритме и выбранном языке программирования Borland С ++ Builder версии 6.0, стандарта ISO/IEC 144882, была написана программа.

            Тело программы состоит из главной функции и четырех впомогательных.

Программа начинается с подключения стандартных библиотек (iostream и conio).

Далее в программе определяется максимальная размерность массива. После определения данной величины, производится определение глобальных массивов:

-mass;

-TempMass.

Далее производится объявление вспомогательных функций:

- void Vvod(float a[n][n],float b[n][n],int n) - данная функция преднащначена для инициализации массива;

-void Vivod(float a[n][n],int n) – данная функция выводит массив с результатами вычислений;

- void Obnul(float a[n][n],int n,int I) - функция предназначенная для отбрасывания пройденных верщин;

-void ZapTempMass(float a[n],int I,int J,int n) – данная функция записывает данные во временный массив.

Далее следует главная функция. Данная функция начинается с определения величин необходимых в ходе решения:

int Otvet[n] - данный массив предназначен для записи в него найденных вершин, которые будут являться ответом.

int size;        - величина инициализирующаяся числом количества вершин

float L[n] - массив, содержащий данные о расстояния между определяемыми вершинами;

float min(0) - временная величина, предназначенная для отыскания минимального расстояния между вершинами;

int i=1-  исходная вершина по умолчанию;

int j - величина  используемая для перебора в массиве;

int s(0) - счетчик итераций.

Далее программа предлогает пользователю ввести количетво вершин.

Посде получения программой данной величины, она создает массив, который далее будет инициализироваться величиной расстояния между вершинами.

После получения программой всех начальных данных, ей будет предложено ввести начальную вершину. После получения программой данной величины, она приступает к решению поставленной ей задачи. Организуется счётчик итераций. На каждой из них происходит вычисление промежуточных значений, которые потом заносятся в массив TempMass и выводятся на экран. После этого массив обнуляется. На каждой итерации выбирается минимальное значение расстояния TempMin, которое определяет дальнейшую строку, по которой будем работать.

while(s<size) – операция будет продолжаться до тех пор, пока количество итераций не станет равным количеству вершин. При выполнении последнего условия выводится конечный результат. Для завершения надо нажать кнопку Ввод. В конце программного кода идёт определение всех четырёх вспомогательных функций.

 

 Выводы:

1) Произведённые  в предыдущих главах исследования  позволили составить    

     алгоритм  поиска кратчайшего  расстояния;

2) Обоснован  выбор языка программирования;

3) На основе составленного алгоритма составлена программа поиска   

    расстояния. 

           3. Экспериментальное исследование алгоритма и  

                  программы.

          3.1 Решение задачи методом Дейкстры.         

            Рассмотрим действие алгоритма на примере. Пусть дан граф G, показанный на рисунке 3.1.1, где каждое неориентированное ребро рассматривается как пара противоположно ориентированных дуг равного веса. Матрица смежности весов С приведена ниже. Требуется найти все кратчайшие пути от вершины x, ко всем остальным вершинам. Для решения задачи воспользуемся алгоритмом Дейкстры, который является одним из самых быстрых для поиска кратчайшего расстояния от некоторой вершины до всех остальных.

 

Рисунок 3.1.1-  Смешанный граф

            Решение.

            Постоянные пометки будем снабжать знаком +, остальные пометки рассматриваются как временные.

            Шаг 1.

                        l(x ) = 0 ,   l(x ) = ∞ , x x , p = x .

            

            Первая итерация

            Шаг 2.

                        Г( p) = Г(x ) = { x } – все пометки временные.

            Применяя  (2)  , получим

                                               l(x ) = min { ; 0+4}= 4,

            Так как на первой итерации  вершина только одна , то шаг  3 по выбору минимума опускается.

            Шаг 4.

                                                 l(x )=4 ; p= x .

            Шаг 5.

            Не все вершины имеют постоянные пометки.

            Переход к следующей итерации. 

                    

     Таблица 3.1.1- Матрица смежности весов .

 

            Вторая итерация.

           Шаг 2.

                                               Г( p) = Г(x ) = { x , x , x , x }.

                                               l(x ) = min { ; 4+3}= 7,

                                               l(x ) = min { ; 4+2}= 6,

                                               l(x ) = min { ; 4+3}= 7.

              Шаг 3.

                                    min{l(x ); l(x ); l(x )} = min{7,6,7} = 6.

              Шаг 4.

                                                   l(x ) = 6 ; p = x .

            Шаг 5. Переход к следующей итерации.

            Третья итерация.

            Шаг 2.

                                               Г( p) = Г(x ) = { x , x , x }.

                                                l(x ) = min {7; 7+4} = 7,

                                               l(x ) = min {7; 6+2} = 7.

            Шаг 3.

                                    min{l(x );  l(x )} = min{7,7} = 7.

            Выбираем любую вершину.

                

            Шаг 4.

                                                    l(x ) = 7 ; p = x

            Шаг 5. Переход к следующей итерации.

           Четвёртая итерация.

            Шаг 2.

                                               Г( p) = Г(x ) = { x , x , x , x }.

                                               l(x ) = min { ; 7+5} = 12.

                                                l(x ) = min {7; 6+2} = 7. 

            Шаг 3.

                                    min{ l(x ); l(x ) }= min{7,12} = 7. 

                

            Шаг 4.

                                                    l(x ) = 7 ; p = x

            Шаг 5. Переход к следующей итерации. 

            Пятая итерация.

            Шаг 2.

                                      Г( p) = Г(x ) = { x ,x , x , x }. 

                                      l(x ) = min { ; 7+3}=10.