Текст програми написаної  на основі алгоритму  Дейкстра

     

/* Алгоритм  пошуку дерева найкоротших шляхів  у зваженому графі  */

/* Е.Дейкстра 1959 р.                                           */ 

#include <stdio.h>

#include <stdlib.h>

#include <float.h> 

int load_matrix(int n, double* weigh);       /* Уведення матриці ваг  */

int deik(int n, int s, double* weigh, int* Q, double* L);  /* Алгоритм пошуку   */

void print(int n, int* Q, double* L);        /* Висновок результату   */ 

void main(void){

      int n=0,s=0,ret=0;

      double *weigh;

      int* Q;  /* Масив міток покажчиків на попередню вершину  */

      double* L; /* Масив найдених ваг шляху до вершини     */ 

      printf("\nАлгоpитм  пошуку дерева найкоротших шляхів  у зваженому графі.\n");

      printf("Е.Дейкстpа, 1959 р.\n");

      printf("\nВведіть  кількість вершин..");

      scanf("%d",&n);

      if (n <= 1){

            printf("\nКількість  вершин повинне бути більше одиниці!\n");

            exit(1);

      }

      printf("\nВведіть  початкову вершину..");

      scanf("%d",&s);

      s--;

      if ((s < 0)||(s > (n-1))){

            printf("\nПочаткова  вершина зазначена неправильно! \n");

            exit(1);

      } 

      Q=malloc(n*sizeof(int));

      L=malloc(n*sizeof(double));

      weigh=malloc(sizeof(double)*n*n);

      if ((weigh == NULL)||(Q == NULL)||(L == NULL)){

            printf("\nHедостатньо  пам'яті для завантаження масиву! \n");

            exit(2);

      }

      ret=load_matrix(n,weigh);

      if (ret != 0){

            printf("\nПомилка введення даних!\n");

            exit(5);

      }

      ret=deik(n,s,weigh,Q,L);

      if (ret != 0){

            switch (ret){

                  case 1 :

                        printf("\nГpаф не є зв'язаним!\n");

                        exit(3);

                  case 2 :

                        printf("\nHедостаточно пам'яті для роботи!\n");

                        exit(4);

            }

      }

      print(n,Q,L);

      free(weigh);

      free(Q);

      free(L);

} 

int load_matrix(int n, double* weigh){

      int i,j,k;

      double tmp;

      for (i=0; i < n; i++){

            for (j=0; j < n; j++){

                  weigh[n*i+j]=(-1);

            }

      }

      printf("\nВведіть  послідовно ваги ребер для  зазначених чи вершин -1 для несуміжних.");

      for (i=0; i < n; i++){

            for (j=i+1; j < n; j++){

                  printf("\nВеpшини %d і %d ",i+1,j+1);

                  k=scanf("%lf",&tmp);

                  if (k != 1){return(1);}

                  weigh[i*n+j]=tmp;

            }

      }

      return(0);

} 

int deik(int n,int s, double* weigh, int* Q, double* L){

      int i,j,k;

      int* QI;  /* Масив індикаторів сталості міток покажчиків */

      double tmp; 

      QI=calloc(n,sizeof(int));

      if (QI == NULL){return(2);} 

      QI[s]=1;

      for (i=0; i < n; i++){

            Q[i]=(-1);

            L[i]=DBL_MAX;

      }

      Q[s]=s;

      L[s]=0;

      weigh[n*(n-1)+s]=0; 

      for (k=0; k < n; k++){    /* Основний цикл по вершинах  */

            for (i=0; i < n; i++){    /* Цикл по рядках матриці ваг */

                  for (j=i+1; j < n; j++){  /* Цикл по стовпцях матриці ваг */

            if ((QI[i]+QI[j] == 1)&&

                  (QI[i]*QI[j] == 0)&&

                  (weigh[i*n+j] != (-1.0))&&

                  (((QI[i] == 1)&&((L[i]+weigh[i*n+j]) < L[j]))||

                  ((QI[j] == 1)&&((L[j]+weigh[i*n+j]) < L[i])))){

                        if (QI[i] == 1){

                              L[j]=L[i]+weigh[i*n+j];

                              Q[j]=i;

                        }

                        else{

                              L[i]=L[j]+weigh[i*n+j];

                              Q[i]=j;

                        }

                  }

            }

      }

      for (tmp=DBL_MAX,i=0; i < n; i++){

            if ((tmp > L[i])&&(QI[i] == 0)){

                  tmp=L[i];

                  j=i;

            }

      }

      QI[j]=1;

      }

      free(QI);

      return(0);

} 

void print(int n, int* Q, double* L){

      int i;

      printf("\n\nДеpево найкоротших шляхів:");

      for (i=0; i < n; i++){

            printf("\nВеpшина: %d  Предок: %d  Вага: %5.2lf",i+1,Q[i]+1,L[i]);

      }

}* 

    Результат виконання програми 

Алгоритм  пошуку дерева найкоротших шляхів у  зваженому графі.

Е.Дейкстра, 1959 р. 

Уведіть кількість вершин.. 6

Уведіть початкову вершину.. 6

Уведіть послідовно ваги ребер для зазначених чи вершин -1 для несуміжних.

Вершини 1 і 2   2

Вершини 1 і 3  -1

Вершини 1 і 4   2

Вершини 1 і 5  -1

Вершини 1 і 6   5

Вершини 2 і 3   2

Вершини 2 і 4  -1

Вершини 2 і 5   2

Вершини 2 і 6  -1

Вершини 3 і 4  -1

Вершини 3 і 5  -1

Вершини 3 і 6   12

Вершини 4 і 5   1

Вершини 4 і 6   2

Вершини 5 і 6   5  

Дерево  найкоротших шляхів:

Вершина: 1  Предок: 4  Вага:  4.00

Вершина: 2  Предок: 5  Вага:  5.00

Вершина: 3  Предок: 2  Вага:  7.00

Вершина: 4  Предок: 6  Вага:  2.00

Вершина: 5  Предок: 4  Вага:  3.00

Вершина: 6  Предок: 6  Вага:  0.00* 
 
 

Графічне  зображення початкового  графа та дерева мінімальних  шляхів після виконання  програми 

 
 

4.Висновок 

  Ця  курсова робота показує що дискретна  математика, поряд з такими класичними розділами математики, як математичний аналіз, диференціальні рівняння, у  навчальних планах спеціальності "Прикладна  математика" і різні розділи  по математичній логіці, алгебрі, комбінаториці і теорії графів тісно пов’язані із сучасним програмуванням. Причини цього неважко зрозуміти, просто розглянувши задачу, у цій курсовій роботі, яка за допомогою алгоритму Е. Дейкстра має змогу пошуку найкоротшого шляху в графі . 
 
 
 

5.Література

1. Зыков А.А. Теорія кінцевих графів. - Новосибірськ: Наука, 1969.
2. Харари Ф. Теорія графів. - М.: Світ, 1973.
3. Зыков А.А. Основи теорії графів. - М.: Наука, 1987.
4. Кристофидес Н. Теорія графів. Алгоритмічний підхід. - М.: Світ, 1978.
5. Майника Э. Алгоритми оптимізації на мережах і графах. - М.: Світ, 1981.
6. Ловас Л., Пламмер М. Прикладні задачі теорії графів. Теорія паросочетаний у математику, фізику, хімії. - М.: Світ, 1998.