Кроме
стандартных функций из библиотек 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
ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЯ
При
запуске программы на экране появится окно с инструкциями. Выполняйте эти
инструкции, а именно:
1.
Введите количество вершин исследуемого графа.
2.
Введите веса рёбер (положительное число). В
программе расстояния от хi до xi+1
и xi+1
до хi считаются равными, а
расстояния от хi до хi
– не существующими. Если ребра между указанными вершинами не существует,
введите 0 (ноль).
На
экран выводится матрица смежности, отображающая введённую информацию.
3.
Введите номер вершины, от которой начинается
искомый путь.
4.
Введите номер вершины, в которой путь
заканчивается.
5.
Чтоб завершить работу программы после получения
результата нажмите Enter.
ЗАКЛЮЧЕНИЕ
Таким
образом, в процессе создания данного проекта разработана программа, реализующая
алгоритм Дейкстры в Microsoft Visual C++ 6.0. Её недостатком является
примитивный пользовательский интерфейс. Это связано с тем, что программа
работает в консольном режиме, не добавляющем к сложности языка сложность
программного оконного интерфейса
Также
были углублены знания, полученные в процессе выполнения лабораторных работ по
предмету «Программирование».
ПЕРЕЧЕНЬ
ССЫЛОК
1. Бондарев
В.М. Программирование на С++.–Х: «Компания СМИТ», 2004
2. Страуструп
Бьярн Язык программирования С++(2 ч).–«К:ДиаСофт», 1993
3. Хаханов
В.И., Чумаченко С.В. Дискретная математика (теоретическое и практическое
содержание курса).–Кафедра АПВТ, 2002
4. Алгоритм
Дейкстры
5. Конспект
лекций.
Приложение
А
Текст программы
#include<iostream.h>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#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<n;i++)
if(!(flag[i]))
result=i;
for(i=0;i<n;i++)
if((l[result]>l[i])&&(!flag[i]))
result=i;
return
result;
}
word
minim(word x, word y)
{
if(x<y)
return x;
return
y;
}
void
main()
{
cout<<"Vvedite
kolichestvo tochek: ";
cin>>n;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
c[i][j]=0;
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
cout<<"Vvedite rasstoyanie ot x"<<i+1<<" do
x"<<j+1<<": ";
cin>>c[i][j];
}
cout<<"
";
for(i=0;i<n;i++)
cout<<" X"<<i+1;
cout<<endl<<endl;
for(i=0;i<n;i++)
{
printf("X%d",i+1);
for(j=0;j<n;j++)
{
printf("%6d",c[i][j]);
c[j][i]=c[i][j];
}
printf("\n\n");
}
for(i=0;i<n;i++)
for(j=0;j<n;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."<<endl;
