2020-01-14
106
1) Вводим количество вершин неориентированного графа.
2) Если количество вершин больше 5, то переходим к пункту 3; иначе переходим к пункту 4.
3) Генератором случайных чисел произвольно задаются связи между вершинами в матрице смежностей, переходим к пункту 5.
4) Вводим связи между вершинами, исходя из следующего условия:
- если не существует пути длиной в одно ребро из одной вершины в другую, то ставим «100»,
- если существует путь между двумя вершинами, то ставим произвольное положительное ненулевое значение веса дуги.
Все введенные данные заносятся в матрицу смежностей.
5) Вводим номера вершин, путь между которыми нужно найти.
6) Задаем начальные значения длин путей равных 100 (в программе это обозначает бесконечность), а пометки всех вершин обнуляем.
7) Для начальной вершины в матрицу, хранящую пути (предшествующие вершины), заносим значение нуль, поскольку нет вершин предшествующих началу, значению пути присваиваем значение нуля, пометку на вершину устанавливаем в единицу.
8) Измененяем длины путей между вершинами «i» и начальной при условии, что рассматриваемая дуга не идет из вершины в саму себя и пометка этой вершины равна нулю, то тогда:
а) просматриваем длину пути в вершину «i» и сравниваем с длиной пути из начальной вершины «Nac»
б) получаем, что длина пути из вершины «s» меньше начального значения пути в вершину «i», то запоминаем в T[i] – ом элементе новую длину пути (меньшую) и H[i] – му присваиваем значение «s».
9) Присваиваем переменной ‘t» значение 100 (бесконечность), а переменной для хранения текущей вершины «k» присваиваем значение нуль.
10) Производим попытку уменьшить длину пути. Если вершина не помечена (ее пометка равна нулю), то если длина пути меньше значения «t» то значению «t» присваиваем текущее значение пути, а переменной для хранения текущей вершины «k» даем значение этой переменной.
11) Если переменная для хранения текущей вершины имеет значение нуля, то пути нет, переходим к пункту 14, иначе переходим к пункту 12.
12) Если переменная для хранения текущей вершины имеет значение конечной вершины, то путь найден, он кратчайший, переходим к пункту 14, иначе переходим к пункту 13.
13) Пометку на вершину, которую хранит переменная «k», изменяем на единицу и переходим к пункту 8.
14) Выводим на экран сообщение о длине пути между вершинами, если такой путь существует (т.е. путь имеет неотрицательную длину).
Экранная форма интерфейса и инструкция пользователя
|
|
Пункты меню:
1. Алгоритм реализации поставленной задачи.
2. Изображение исходного графа.
3. Выход из программы.
Для выбора пункта необходимо нажать на соответствующую клавишу:
- если это пункт 1, то нажмите «A» или «a»;
- если это пункт 2, то нажмите «D» или «d»;
- если это пункт 3, то нажмите «E» или «e».
Заключение
В соответствии с поставленной задачей в курсовой работе было выполнено следующее:
1) Изучен конкретный раздел дискретной математики.
2) Решены 5 задач по изученной теме с методическим описанием.
3) Разработан и реализован в виде программы алгоритм по изученной теме. Разработан программный интерфейс.
Литература
1. Новиков Ф.А. Дискретная математика для программистов – СПб.: Питер, 2002 год
1. Немнюгин С.А. Turbo Pascal: практикум – СПб.: Питер, 2002 год
