Теория графов
2. Описание алгоритма решения задачи
Программа выводит минимальный путь между двумя указанными вершинами в графе и его длину.
При запуске программы на экран выводится запрос о вводе весов рёбер исследуемого графа. Данные, введённые пользователем, отображаются в виде матрицы смежности, в которой не существующие рёбра обозначаются нулями. После указанным рёбрам присваивается значение 65535, которое принимается за бесконечность. Следующим этапом выполнения программы является запрос о вводе номеров вершин, между которыми необходимо узнать путь. В случае, если начальная и конечная вершины совпадают, отображается соответствующее сообщение и работа программы завершается. В противном случае выполняется непосредственно алгоритм Дейкстры, схема которого приведена в приложении. Результатом программы является вывод на экран вершин, через которые проходит минимальный путь, а также вывод длины маршрута. Если пути между заданными точками не существует - выводится соответствующее сообщение.
Описание использованных программных средств
Переменная |
Тип |
Описание |
|
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 были использованы также следующие функции.
· word minim(word x, word y) - функция, которая возвращает минимальное из x и y.
· int min(int n) - функция, которая возвращает номер элемента массива l[i] минимальной "неотмеченной" длиной пути(flag[i]=0).