Главная » Алгоритм Дейкстры. Алгоритм Форда-Беллмана
22:08

Алгоритм Дейкстры. Алгоритм Форда-Беллмана


Алгоритм Дейкстры. Алгоритм Форда-Беллмана. Язык: С

Сегодня разберем два алгоритма для поиска минимального пути от любой вершины графа до любой другой вершины.

Первый алгоритм - Дейкстры.  

Алгоритм работает только для графов без ребер отрицательного веса.

Второй алгоритм - Форда-Беллмана. 

В отличие от предыдущего алгоритма, этот работает при наличии в графах ребер отрицательного веса.  Алгоритм также позволяет узнать есть ли в графе отрицательный цикл. Если вместо  |V| - 1  итераций сделать |V| итераций цикла и длина кратчайшей пути до какой-либо вершины уменьшилась, то граф содержит отрицательный цикл.

|V| - число ребер в графе.


На входе программы: файл, в первой строке которой - порядок матрицы, далее идет матрица смежности взвешенного графа.

На выходе:  массив с расстояниями от заданной вершины до всех остальных,  если пути нет, то выводим "INF".

Также программа считает время выполнения алгоритмов и выводит на экран.

Программа реализована в visual studio 2017 

Скачать примеры тест-файлов


Реализация на языке Си: 


  1. #include "stdio.h"
  2. #include "malloc.h"
  3. #include "locale.h"
  4. #include "time.h"
  5. #define INF 1000000000
  6.  
  7. void output(int count, int* result, int apex, int mode)
  8. {
  9.     int i;
  10.     if ( mode == 0)
  11.         printf("Дейкстра:\n");
  12.     else
  13.         printf("Форд-Баллман:\n");
  14.     for (i = 0; i < count; i++)
  15.     {
  16.         if (result[i] < 10000)  //если путь есть
  17.             printf("Минимальное расстояние между вершинами %d и %d = %d\n", apex, i, result[i]);
  18.         else
  19.             printf("Минимальное расстояние между вершинами %d и %d = INF\n", apex, i);
  20.     }
  21. }
  22.  
  23. void Ford_Ballman(int CountApex, int** SourceMatrix, int Start)
  24. {
  25.     int *MinPath; // массив кратчайших путей
  26.     int i,j,k;
  27.     int count = 0;
  28.     MinPath = (int*)malloc(CountApex * sizeof(int));
  29.     for (i = 0; i<CountApex; i++)
  30.     {
  31.         MinPath[i] = INF; //изначально кратчайшие пути неизвестны
  32.     }
  33.     MinPath[Start] = 0;
  34.     for (k = 0; k<CountApex; k++)
  35.     {
  36.         for (i = 0; i < CountApex; ++i)
  37.         {
  38.             for (j = 0; j < CountApex; ++j)
  39.             {
  40.                 if (SourceMatrix[i][j] != 0) //если вершину не посещали
  41.                     if (MinPath[j] > MinPath[i] + SourceMatrix[i][j])
  42.                         MinPath[j] = MinPath[i] + SourceMatrix[i][j];
  43.             }
  44.         }
  45.     }
  46.     output(CountApex, MinPath, Start, 1);
  47. }
  48. void deikstra(int CountApex, int** SourceMatrix, int Start)
  49. {
  50.     int *metka; // массив меток
  51.     int *MinPuth; // массив кратчайших путей
  52.     int temp, i;
  53.     int minindex, min;
  54.     metka = (int*)malloc(CountApex * sizeof(int));
  55.     MinPuth = (int*)malloc(CountApex * sizeof(int));
  56.     for (i = 0; i<CountApex; i++) {
  57.         MinPuth[i] = INF;
  58.         metka[i] = 1;
  59.     }
  60.     MinPuth[Start] = 0;
  61.     do { // исполнение алгоритма 
  62.         minindex = INF;
  63.         min = INF;
  64.         for (i = 0; i<CountApex; i++) {
  65.             if ((metka[i] == 1) && (MinPuth[i]<min)) {
  66.                 min = MinPuth[i];
  67.                 minindex = i;
  68.             }
  69.         }
  70.         if (minindex != INF) {
  71.             for (i = 0; i<CountApex; i++) {
  72.                 if (SourceMatrix[minindex][i] > 0) {
  73.                     temp = min + SourceMatrix[minindex][i];
  74.                     if (temp < MinPuth[i])
  75.                         MinPuth[i] = temp;
  76.                 }
  77.             }
  78.             metka[minindex] = 0;
  79.         }
  80.     } while (minindex < INF);
  81.     output(CountApex, MinPuth, Start, 0);
  82. }
  83. int main(int argc, char* argv)
  84. {
  85.     int apex;
  86.     int CountApex;
  87.     int **mputh;
  88.     int i, j, E=0;
  89.     int negative = 0;
  90.     float start, end;
  91.     setlocale(LC_ALL, "Rus");
  92.     FILE *in;
  93.     char filename[20];
  94.     printf("Введите имя файла: ");
  95.     scanf_s("%s", filename, 20);
  96.     fopen_s(&in, filename, "r");
  97.     if (!in)
  98.         printf("Ошиба! Файл не прочитан");
  99.     else
  100.         printf("Читаем граф!\n");
  101.     fscanf_s(in, "%d", &CountApex);
  102.     mputh = (int **)malloc(CountApex * sizeof(int *));
  103.     for (int i = 0; i < CountApex; i++) {
  104.         mputh[i] = (int *)malloc(CountApex * sizeof(int));
  105.     }
  106.     for (i = 0; i < CountApex; i++)
  107.     {
  108.         for (j = 0; j < CountApex; j++)
  109.         {
  110.             fscanf_s(in, "%d", &mputh[i][j]);
  111.             if (mputh[i][j] < 0)
  112.                 negative++;
  113.         }
  114.     }
  115.     printf("Граф считан\n");
  116.     printf("Введите вершину, от которой ведем отсчет: ");
  117.     scanf_s("%d", &apex);
  118.         start = clock();
  119.         deikstra(CountApex, mputh, apex);
  120.         end = clock();
  121.         printf("Алгоритм использовал %.10f секунд.\n", (end - start) / (CLOCKS_PER_SEC));
  122.         if(negative!=0)
  123.             printf("Матрица содержит ребра с отрицательным весом, алгоритм Дейкстры может работать некорректно\n");
  124.     printf("\n\n");
  125.     start = clock();
  126.     Ford_Ballman(CountApex, mputh, apex);
  127.     end = clock();
  128.     printf("Алгоритм использовал %.10f секунд.\n", (end - start) / (CLOCKS_PER_SEC));
  129.     getchar();
  130.     getchar();
  131.     return 0;
  132. }

Пример работы программы:



Похожие материалы:
Нашли ошибку на сайте? Напишите в комментариях!
Категория: Язык программирования: Си/Си++ | Просмотров: 51 | | Рейтинг: 5.0/1