Теория графов

курсовая работа

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).

Делись добром ;)