Содержание 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

1. Постановка  задачи

 

 Дан неориентированный взвешенный граф G (V,E). Веса всех рёбер неотрицательны. Указана некоторая стартовая вершина a и конечная вершина u. Требуется написать программу, которая находит кратчайшее расстояние и выводит кратчайший путь от вершины a до вершины u. 

 

 

2. Анализ задачи, выбор способа представления данных

 

 В результате анализа условия задачи было решено представить граф G (V,E)  с помощью матрицы B размером , которая состоит из элементов таких что:

 

 В программе матрицу B будем хранить в двумерном динамическом массиве размером . 

 

 

3. Алгоритмы решения  задачи

 

 Введем  следующие обозначения:

• - множество вершин графа;
• - множество ребер графа;
• - вес ребра ;
• - вершина, расстояния от которой ищутся;
• - множество посещенных вершин;
• - по окончании работы алгоритма равно длине кратчайшего пути из до вершины ;
• - по окончании работы алгоритма содержит кратчайший путь из в .

 Приведем  описание алгоритма решения поставленной задачи (см. алгоритм 1): 

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

 Присвоим

 Для всех и отличных от

             Присвоим

 Пока

             Пусть - вершина с минимальным

             Для всех таких что

                   если то

                         изменим

                         изменим  

 Для хранения чисел  будем использовать массив чисел, а для хранения принадлежности элемента множеству - массив булевых переменных.

 В начале алгоритма расстояние для  начальной вершины полагается равным нулю, а все остальные расстояния заполняются большим положительным  числом (большим максимального возможного пути в графе). Массив булевых переменных заполняется нулями. Затем запускается основной цикл.

 На  каждом шаге цикла мы ищем вершину  с минимальным расстоянием и  флагом равным нулю. Затем мы устанавливаем в ней флаг 1 и проверяем все соседние с ней вершины. Если до соседней вершины расстояние больше, чем сумма расстояния до текущей вершины и длины ребра, то уменьшаем его. Цикл завершается, когда флаги всех вершин становятся равны 1, либо когда у всех вершин с флагом 0 . Последний случай возможен, если и только если граф G несвязан.

 

4. Реализация программы

 

 Программа, решающая поставленную задачу, была реализована  в среде разработки Visual Studio 2005 на языке программирования С++. 

 4.1 Именованные константы 

 Разработанная программа включает именованные константы, перечисленные в таблице 1: 

 Таблица 1 – Именованные константы

 

 4.2 Функции 

 Основные  функции, используемые в программе, сведены в таблицу 2. 

 Таблица 2 – Основные функции

 

 

 

5. Руководство пользователя

 

 Программа вводит входные данные из текстового файла input.txt. В первую строку входного файла необходимо ввести количество вершин в графе. Во вторую строку вводится (через пробел) начальная вершина и конечная. Далее вводится матрица, характеризующая граф (все элементы матрицы разделяются пробелом).

 После запуска программы на экране компьютера отобразится консольное окно с результатом.

 Список  использованных источников.

1. Кормен , Т. Алгоритмы: построение и анализ, 2-е  издание. - М. : издательский дом "Вильяме", 2005.
2. Седжвик , Р. Фундаментальные алгоритмы на C++. Алгоритмы на графах. - СПб.: "ДиаСофтЮП", 2002.

 

 Приложение А – Текст программы 

 // Подключаем  заголовочный файл для работы  со стандартными потоками cin и  cout

 #include "iostream"

 // Подключаем  заголовчный файл для работы  с потоковыми файловыми классами

 #include "fstream"

 using namespace std;

 const int INF = 1000000;

 void PrintShortestPathDistance (double* CurLenght, int Index)// Функция осуществляет  вывод кратчайшего расстояния

 {

       cout << "Shortest path distance : " << endl;

       cout << CurLenght [Index] << endl;

 }

 void PrintShortestPath (int* AncestorsArray,int SourceVertex,int EventualVertex) // Функция осуществляет вывод кратчайшего пути

 {

       cout << EventualVertex << " <-- ";

             for (int i = EventualVertex - 1; AncestorsArray[i] != SourceVertex; i = AncestorsArray[i - 1])

                   cout << AncestorsArray[i] << " <-- ";

       cout << SourceVertex << endl;

 }

 void SearchShortestPath (double* CurLenght,double** AdjacencyMatrix,int* AncestorsArray,bool* Used,int AmountOfVertex)// Функция поиска кратчайшего  расстояния и пути

 {

       for (int i = 0; i < AmountOfVertex; i++)

       {

             // Поиск вершины  до которой расстояние минимально

             int MinIndex = AmountOfVertex;

             for (int j = 0; j < AmountOfVertex; j++)

             {

                   if (CurLenght [j] <= CurLenght [MinIndex] && !Used [j])

                               MinIndex = j;

             }

             // Если минимальной  выбрана вершина расстояние до которой равно бесконечности то выходим из цикла

             if (CurLenght [MinIndex] == INF)

                   break;

             // Обозначаем текущую  вершину как посещенную

             Used [MinIndex] = true;

             // Релаксация

             for (int j = 0; j < AmountOfVertex; j++)

             {

                   if (AdjacencyMatrix [MinIndex][j]!= 0 && !Used [j] && (CurLenght[MinIndex] + AdjacencyMatrix [MinIndex][j] < CurLenght [j]))

                   {

                         // Улучшаем расстояние  до выбранной вершины

                         CurLenght [j] =  CurLenght[MinIndex] + AdjacencyMatrix [MinIndex][j];

                         // Сохраняем предыдущую вершину для выбранной

                         AncestorsArray [j] = MinIndex + 1;

                   }

             }

       } 

 }

 int main ()

 { 

       ifstream f ("input.txt");

       int AmountOfVertex,SourceVertex,EventualVertex;

       // Вводим количество вершин

       f >> AmountOfVertex;

       // Вводим начальную и конечную вершину

       f >> SourceVertex >> EventualVertex;

       //Массив  для хранения текущей длины  до каждой вершины

       double* CurLenght = new double [AmountOfVertex + 1];

       // Устанавливаем расстояние до  каждой вершины равное бесконечности

       for (int i = 0; i < AmountOfVertex + 1; i++)

             CurLenght [i] = INF;

       // Расстояние до начальной вершины  равно 0

       CurLenght [SourceVertex - 1] = 0;

       // Матрица смежности

       double** AdjacencyMatrix = new double* [AmountOfVertex];

       for (int i = 0; i < AmountOfVertex; i++)

             AdjacencyMatrix [i] = new double [AmountOfVertex];

       // Считываем матрицу смежности

       for (int i = 0; i < AmountOfVertex; i++)

             for (int j = 0; j < AmountOfVertex; j++)

                   f >> AdjacencyMatrix [i][j];

       // Булевый массив для хранения  посещенных вершин

       bool* Used = new bool [AmountOfVertex];

       // На данном этапе все вершины  являются непосещенными 

       for (int i = 0; i < AmountOfVertex; i++)

             Used [i] = false;

       // Массив предков

       int* AncestorsArray = new int [AmountOfVertex];

       // Полагаем что предыдущей вершины  для конечной вершины не существует

       AncestorsArray[EventualVertex - 1] = -1;

       // Вызываем функцию поиска кратчайшего  пути

       SearchShortestPath (CurLenght,AdjacencyMatrix,AncestorsArray,Used,AmountOfVertex);

       // Выводим кратчайшее расстояние

       PrintShortestPathDistance (CurLenght, EventualVertex-1);

       // Выводим кратчайший путь, если  вершина не изолированна, в противном  случае сообщаем об этом

       if (AncestorsArray[EventualVertex - 1] >= 0)

       {

             cout << "Shortest path : " << endl;

             PrintShortestPath (AncestorsArray,SourceVertex,EventualVertex);

       }

       else cout << "Vertex isolated" << endl;

       // Освобождаем память

       delete[] CurLenght;

       for (int i = 0; i < AmountOfVertex; i++)

             delete[] AdjacencyMatrix [i];

       delete[] AdjacencyMatrix;

       delete[] Used;

       delete[] AncestorsArray;

       return 0;

 }