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

При написании программы использовалась среда Microsoft Visual C++ 6.0. Данная среда позволяет писать приложения на языке C++.

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

Окно программы разделено на несколько частей. Вверху находится стандартная панель – Standart, с которой можно сохранить исходный текст программы на диск, открыть новый документ, скопировать или вставить текст, отменить последнее действие, или найти текст. Слева находятся панели ObjectTreeView и ObjectInspector, на которых показаны объекты, которые используются в данной программе, и их свойства. В центре окна программы расположен текстовый редактор, в котором следует писать программу. Внизу – панель Output, в которой показывается сообщения, если в программе содержатся ошибки – компилятор сообщает вид ошибки и строку, в которой она допущена, достаточно сделать двойной кликлевой клавишеймыши на описании ошибки в Output, чтобыпереместиться на строку, содержащую ошибки.

Программа создана в консольном режиме – в режиме, не имеющем графического интерфейса.

4 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ

4.1 Описание алгоритма и структуры программы

Рис. 4.1.1

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

При запуске программы на экран выводится запрос о вводе весов рёбер исследуемого графа. Данные, введённые пользователем, отображаются в виде матрицы смежности, в которой не существующие рёбра обозначаются нулями. После указанным рёбрам присваивается значение 65535, которое принимается за бесконечность.

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

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

4.2 Описание использованных программных средств

Таблица 4.2.1–Описание переменных

Переменная	Тип	Описание
n	int	Количество точек (вершин) грифа
i,j	int	Счётчики
p	int	Номер кратчайшего пути и наименьшей длины пути
xn	int	Номер начальной точки (вершины)
xk	int	Номер конечной точки (вершины)
flag[11]	int	Массив, i-й элемент которого имеет значение 0, когда i-й путь и расстояние временные, и принимает значение 1, когда i-й путь и расстояние становятся постоянными
c[11][11]	word (unsigned int)	Массив i-j элемент которого содержит расстояние между i-й и j-й точками (вершинами) Замечание: 1. с[i][i]=¥ 2. c[i][j]=c[j][i]
s[80]	char	Строчная переменная, которая содержит промежуточные значения пути
path[80][11]	char	Массив строк, который содержит пути Замечание: После прохождения обработки по алгоритму Дейкстры p-й элемент массива содержит кратчайший путь.
l[11]	word (unsigned int)	Массив, который содержит длины путей (path) Замечание: После прохождения обработки по алгоритму Дейкстры p-й элемент массива содержит длину кратчайшего пути.

Кроме стандартных функций из библиотек iostream.h, string.h, stdio.h, conio.h были использованы также следующие функции.

· wordminim(wordx, wordy) – функция, которая возвращает минимальное из x и y.

Рис. 4.2.1

· intmin(intn) – функция, которая возвращает номер элемента массива l[i] минимальной «неотмеченной» длиной пути(flag[i]=0).

Рис. 4.2.2

5 ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЯ

При запуске программы на экране появится окно с инструкциями. Выполняйте эти инструкции, а именно:

1.Введите количество вершин исследуемого графа.