Описание использованных программных средств

Таблица 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-й точками (вершинами) Замечание: 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.

Рис. 4.2.1

· int min(int n) – функция, которая возвращает номер элемента массива l[i] минимальной «неотмеченной» длиной пути(flag[i]=0).

Рис. 4.2.2

ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЯ

 

При запуске программы на экране появится окно с инструкциями. Выполняйте эти инструкции, а именно:

1. Введите количество вершин исследуемого графа.

2. Введите веса рёбер (положительное число). В программе расстояния от х_i до x_i+1 и x_i+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;

              getch();

              return;

    }

 

    for(i=0;i<n;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<n;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: "<<path[p+1]<<endl;

              cout<<"Dlina puti: "<<l[p]<<endl;

    }

    else

              cout<<"takogo puti ne syshestvuet!"<<endl;

    getch();

}

Приложение Б

Результат

Приложение В

 

Схема программной реализации алгоритма Дейкстры