Поиск кратчайшего пути в графе (Дейкстра)

c++
  1. /*
  2.  * Input:
  3.  * ~~~~~~~~
  4.  * size=5 start=0 end=4
  5.  * -1   4   6   11  -1
  6.  * 4    -1  10  6   -1
  7.  * 6    10  -1  3   8
  8.  * 11   6   3   -1  4
  9.  * -1   -1  8   4   -1
  10.  * ~~~~~~~~
  11.  * -1 означает бесконечность (нет пути).
  12.  */
  13.  
  14. #include <stdio.h>
  15. #include <stdlib.h>
  16. #include <limits.h>
  17.  
  18. struct Cell {
  19.     int closed; //          A
  20.     int passability; //     B
  21.     struct Cell *parent; // Ind
  22.     char name[5];
  23. };
  24.  
  25. int main(int argc, char** argv) {
  26.     int size, i, j, start, end, min, idx;
  27.     char path[80];
  28.     printf("Путь к файлу данных:\n");
  29.     scanf("%s", path);
  30.     FILE *file = fopen(path, "r");
  31.     if (file == NULL) {
  32.         printf("Ошибка!\n");
  33.         return EXIT_FAILURE;
  34.     }
  35.     fscanf(file, "size=%d start=%d end=%d", &size, &start, &end);
  36.     struct Cell *row = (struct Cell*) malloc(size * sizeof (struct Cell));
  37.     int **C = (int**) malloc(size * sizeof (int*)); // C-matrix
  38.     for (i = 0; i < size; i++) C[i] = (int*) malloc(size * sizeof (int));
  39.     for (i = 0; i < size; i++) {
  40.         for (j = 0; j < size; j++) {
  41.             fscanf(file, "%d", &C[i][j]);
  42.             if (C[i][j] == -1) C[i][j] = INT_MAX;
  43.         }
  44.     }
  45.     fclose(file);
  46.  
  47.     // First part (init)
  48.     row[start].parent = 0;
  49.     row[start].passability = 0;
  50.     row[start].closed = 1;
  51.     for (i = 0; i < size; i++) {
  52.         sprintf(row[i].name, "X%d", i);
  53.         if (i != start) {
  54.             row[i].parent = &row[start];
  55.             row[i].passability = C[start][i];
  56.             row[i].closed = 0;
  57.         }
  58.     }
  59.  
  60.     // Second part (cycle)
  61.     for (i = 0; i < (size - 2); i++) {
  62.         min = INT_MAX, idx = -1;
  63.         for (j = 0; j < size; j++) {
  64.             if (row[j].closed) continue;
  65.             if (min > row[j].passability) {
  66.                 min = row[j].passability, idx = j;
  67.             }
  68.         }
  69.         row[idx].closed = 1;
  70.         for (j = 0; j < size; j++) {
  71.             if (row[j].closed) continue;
  72.             if (row[j].passability > (C[idx][j] == INT_MAX ? INT_MAX : C[idx][j] + row[idx].passability)) {
  73.                 row[j].passability = row[idx].passability + C[idx][j];
  74.                 row[j].parent = &row[idx];
  75.             }
  76.         }
  77.     }
  78.     printf("Длинна пути с %d до %d равна %d\nПуть: ", start, end, row[end].passability);
  79.     struct Cell *cell = &row[end];
  80.     while (cell != 0) {
  81.         printf("%s, ", cell->name);
  82.         cell = cell->parent;
  83.     }
  84.     for (i = 0; i < size; i++) free(C[i]);
  85.     free(C);
  86.     free(row);
  87.     return (EXIT_SUCCESS);
  88. }
Поиск пути методом дейкстры в графе, если граф задан матрицей
Назад

Реклама

Мы в соцсетях

tw tg yt gt