Программа создана в консольном режиме - в режиме, не имеющем графического интерфейса.

 

      4 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ 

     4.1 Описание алгоритма и структуры программы

     

     Рис. 4.1.1

     Программа выводит минимальный путь между двумя указанными вершинами в графе и его длину.

     При запуске программы на экран выводится запрос о вводе весов рёбер исследуемого графа. Данные, введённые пользователем, отображаются в виде матрицы смежности, в которой не существующие рёбра обозначаются нулями. После указанным рёбрам присваивается значение 65535, которое принимается за бесконечность.

     Следующим этапом выполнения программы является запрос о вводе номеров вершин, между которыми необходимо узнать путь. В случае, если начальная и конечная вершины совпадают, отображается соответствующее сообщение и работа программы завершается. В противном случае выполняется непосредственно алгоритм Дейкстры, схема которого приведена в приложении В.

     Результатом программы является вывод на экран вершин, через которые проходит минимальный путь, а также вывод длины маршрута. Если пути между заданными точками не существует - выводится соответствующее сообщение.

 

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

     Таблица 4.2.1-Описание переменных

       

     Кроме стандартных функций из библиотек 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 до x_i+1 и x_i+1 до х_i считаются равными, а расстояния от  х_i до х_i - не существующими. Если ребра между указанными вершинами не существует, введите 0 (ноль).

     На экран выводится матрица смежности, отображающая введённую информацию.

     Введите номер вершины, от которой начинается искомый путь.

     Введите номер вершины, в которой путь заканчивается.

     Чтоб завершить работу программы после получения результата нажмите Enter.

 

      ЗАКЛЮЧЕНИЕ 

     Таким образом, в процессе создания данного проекта разработана программа, реализующая алгоритм Дейкстры в Microsoft Visual C++ 6.0. Её недостатком является примитивный пользовательский интерфейс. Это связано с тем, что программа работает в консольном режиме, не добавляющем к сложности языка сложность программного оконного интерфейса

     Также были углублены знания, полученные в процессе  выполнения лабораторных работ по предмету «Программирование».

 

      ПЕРЕЧЕНЬ ССЫЛОК 

     Бондарев В.М. Программирование на С++.-Х: «Компания СМИТ», 2004

     Страуструп Бьярн Язык программирования С++(2 ч).-«К:ДиаСофт», 1993

     Хаханов В.И., Чумаченко С.В. Дискретная математика (теоретическое и практическое содержание курса).-Кафедра АПВТ, 2002 

     Алгоритм Дейкстры

     Конспект лекций.

 

      Приложение А

     Текст программы

     #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();

     }

 

      Приложение Б

     Результат

     

 

      Приложение В 

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