48265 (Программная реализация алгоритма Дейкстры (построение цепей минимальной длины)), страница 2
Описание файла
Документ из архива "Программная реализация алгоритма Дейкстры (построение цепей минимальной длины)", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "48265"
Текст 2 страницы из документа "48265"
Программа выводит минимальный путь между двумя указанными вершинами в графе и его длину.
При запуске программы на экран выводится запрос о вводе весов рёбер исследуемого графа. Данные, введённые пользователем, отображаются в виде матрицы смежности, в которой не существующие рёбра обозначаются нулями. После указанным рёбрам присваивается значение 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-й точками (вершинами) Замечание:
|
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.
Рис. 4.2.1
-
int min(int n) – функция, которая возвращает номер элемента массива l[i] минимальной «неотмеченной» длиной пути(flag[i]=0).
Рис. 4.2.2
5 ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЯ
При запуске программы на экране появится окно с инструкциями. Выполняйте эти инструкции, а именно:
-
Введите количество вершин исследуемого графа.
-
Введите веса рёбер (положительное число). В программе расстояния от хi до xi+1 и xi+1 до хi считаются равными, а расстояния от хi до хi – не существующими. Если ребра между указанными вершинами не существует, введите 0 (ноль).
На экран выводится матрица смежности, отображающая введённую информацию.
-
Введите номер вершины, от которой начинается искомый путь.
-
Введите номер вершины, в которой путь заканчивается.
-
Чтоб завершить работу программы после получения результата нажмите Enter.
ЗАКЛЮЧЕНИЕ
Таким образом, в процессе создания данного проекта разработана программа, реализующая алгоритм Дейкстры в Microsoft Visual C++ 6.0. Её недостатком является примитивный пользовательский интерфейс. Это связано с тем, что программа работает в консольном режиме, не добавляющем к сложности языка сложность программного оконного интерфейса
Также были углублены знания, полученные в процессе выполнения лабораторных работ по предмету «Программирование».
ПЕРЕЧЕНЬ ССЫЛОК
-
Бондарев В.М. Программирование на С++.–Х: «Компания СМИТ», 2004
-
Страуструп Бьярн Язык программирования С++(2 ч).–«К:ДиаСофт», 1993
-
Хаханов В.И., Чумаченко С.В. Дискретная математика (теоретическое и практическое содержание курса).–Кафедра АПВТ, 2002
-
Алгоритм Дейкстры
-
Конспект лекций.
Приложение А
Текст программы
#include
#include
#include
#include
#include
#define word unsigned int
int i, j, n, p, xn, xk;
int flag[11];
word c[11][11], l[11];
char s[80], path[80][11];
int min(int n)
{
int i, result;
for(i=0;i if(!(flag[i])) result=i; for(i=0;i if((l[result]>l[i])&&(!flag[i])) result=i; return result; } word minim(word x, word y) { if(x return y; } void main() { cout<<"Vvedite kolichestvo tochek: "; cin>>n; for(i=0;i for(j=0;j for(i=0;i for(j=i+1;j { cout<<"Vvedite rasstoyanie ot x"< cin>>c[i][j]; } cout<<" "; for(i=0;i cout< for(i=0;i { printf("X%d",i+1); for(j=0;j { printf("%6d",c[i][j]); c[j][i]=c[i][j]; } printf("\n\n"); } for(i=0;i for(j=0;j if(c[i][j]==0) c[i][j]=65535; //бесконечность cout<<"Vvedite nachalnuy tochku: "; cin>>xn; cout<<"Vvedite konechnuy tochku: "; cin>>xk; xk--; xn--; if(xn==xk) { cout<<"Nachalnaya I konechnaya tochki sovpadayt."< getch(); return; } for(i=0;i { flag[i]=0; l[i]=65535; } l[xn]=0; flag[xn]=1; p=xn; itoa(xn+1,s,10); for(i=1;i<=n;i++) { strcpy(path[i],"X"); strcat(path[i],s); } do { for(i=0;i if((c[p][i]!=65535)&&(!flag[i])&&(i!=p)) { if(l[i]>l[p]+c[p][i]) { itoa(i+1,s,10); strcpy(path[i+1],path[p+1]); strcat(path[i+1],"-X"); strcat(path[i+1],s); } l[i]=minim(l[i],l[p]+c[p][i]); } p=min(n); flag[p]=1; } while(p!=xk); if(l[p]!=65535) { cout<<"Put: "< cout<<"Dlina puti: "< } else cout<<"takogo puti ne syshestvuet!"< getch(); } Приложение Б Результат Приложение В Схема программной реализации алгоритма Дейкстры