Алгоритм Дейкстры нахождения кратчайшего пути

Алгоритмизация / Алгоритм Дейкстры нахождения кратчайшего пути

 

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

Для решения указанной задачи можно использовать алгоритм Дейкстры — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Работает только для графов без рёбер отрицательного веса.

Пусть требуется найти кратчайшие расстояния от 1-й вершины до всех остальных.

Кружками обозначены вершины, линиями – пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначен их вес – длина пути. Рядом с каждой вершиной красным обозначена метка – длина кратчайшего пути в эту вершину из вершины 1.
Задача

Инициализация

Метка самой вершины 1 полагается равной 0, метки остальных вершин – недостижимо большое число (в идеале — бесконечность). Это отражает то, что расстояния от вершины 1 до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные.
Инициализация

Первый шаг

Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6. Обходим соседей вершины по очереди.

Первый сосед вершины 1 – вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1 (значению её метки) и длины ребра, идущего из 1-й во 2-ю, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2 (10000), поэтому новая метка 2-й вершины равна 7.
Шаг 1
Аналогично находим длины пути для всех других соседей (вершины 3 и 6).

Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит. Вершина 1 отмечается как посещенная.

Второй шаг

Шаг 1 алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.

Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4.

Вершина 1 уже посещена. Следующий сосед вершины 2 — вершина 3, так как имеет минимальную метку из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9, а 9 < 17, поэтому метка не меняется.
Шаг 2
Ещё один сосед вершины 2 — вершина 4. Если идти в неё через 2-ю, то длина такого пути будет равна 22 (7 + 15 = 22). Поскольку 22<10000, устанавливаем метку вершины 4 равной 22.

Все соседи вершины 2 просмотрены, помечаем её как посещенную.

Третий шаг

Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим следующие результаты.
Шаг 3

Четвертый шаг

Шаг 4

Пятый шаг

Шаг 5

Шестой шаг

Шаг 6
Таким образом, кратчайшим путем из вершины 1 в вершину 5 будет путь через вершины 1 — 3 — 6 — 5, поскольку таким путем мы набираем минимальный вес, равный 20.

 
Займемся выводом кратчайшего пути. Мы знаем длину пути для каждой вершины, и теперь будем рассматривать вершины с конца. Рассматриваем конечную вершину (в данном случае — вершина 5), и для всех вершин, с которой она связана, находим длину пути, вычитая вес соответствующего ребра из длины пути конечной вершины.
Так, вершина 5 имеет длину пути 20. Она связана с вершинами 6 и 4.
Для вершины 6 получим вес 20 — 9 = 11 (совпал).
Для вершины 4 получим вес 20 — 6 = 14 (не совпал).
Если в результате мы получим значение, которое совпадает с длиной пути рассматриваемой вершины (в данном случае — вершина 6), то именно из нее был осуществлен переход в конечную вершину. Отмечаем эту вершину на искомом пути.
Далее определяем ребро, через которое мы попали в вершину 6. И так пока не дойдем до начала.
Если в результате такого обхода у нас на каком-то шаге совпадут значения для нескольких вершин, то можно взять любую из них — несколько путей будут иметь одинаковую длину.

 

Реализация алгоритма Дейкстры

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

1 2 3 4 5 6
1 0 7 9 0 0 14
2 7 0 10 15 0 0
3 9 10 0 11 0 2
4 0 15 11 0 6 0
5 0 0 0 6 0 9
6 14 0 2 0 9 0

Реализация на C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define SIZE 6
int main()
{
  int a[SIZE][SIZE]; // матрица связей
  int d[SIZE]; // минимальное расстояние
  int v[SIZE]; // посещенные вершины
  int temp, minindex, min;
  int begin_index = 0;
  system("chcp 1251");
  system("cls");
  // Инициализация матрицы связей
  for (int i = 0; i<SIZE; i++)
  {
    a[i][i] = 0;
    for (int j = i + 1; j<SIZE; j++) {
      printf("Введите расстояние %d - %d: ", i + 1, j + 1);
      scanf("%d", &temp);
      a[i][j] = temp;
      a[j][i] = temp;
    }
  }
  // Вывод матрицы связей
  for (int i = 0; i<SIZE; i++)
  {
    for (int j = 0; j<SIZE; j++)
      printf("%5d ", a[i][j]);
    printf("\n");
  }
  //Инициализация вершин и расстояний
  for (int i = 0; i<SIZE; i++)
  {
    d[i] = 10000;
    v[i] = 1;
  }
  d[begin_index] = 0;
  // Шаг алгоритма
  do {
    minindex = 10000;
    min = 10000;
    for (int i = 0; i<SIZE; i++)
    { // Если вершину ещё не обошли и вес меньше min
      if ((v[i] == 1) && (d[i]<min))
      { // Переприсваиваем значения
        min = d[i];
        minindex = i;
      }
    }
    // Добавляем найденный минимальный вес
    // к текущему весу вершины
    // и сравниваем с текущим минимальным весом вершины
    if (minindex != 10000)
    {
      for (int i = 0; i<SIZE; i++)
      {
        if (a[minindex][i] > 0)
        {
          temp = min + a[minindex][i];
          if (temp < d[i])
          {
            d[i] = temp;
          }
        }
      }
      v[minindex] = 0;
    }
  } while (minindex < 10000);
  // Вывод кратчайших расстояний до вершин
  printf("\nКратчайшие расстояния до вершин: \n");
  for (int i = 0; i<SIZE; i++)
    printf("%5d ", d[i]);

  // Восстановление пути
  int ver[SIZE]; // массив посещенных вершин
  int end = 4; // индекс конечной вершины = 5 - 1
  ver[0] = end + 1; // начальный элемент - конечная вершина
  int k = 1; // индекс предыдущей вершины
  int weight = d[end]; // вес конечной вершины

  while (end != begin_index) // пока не дошли до начальной вершины
  {
    for (int i = 0; i<SIZE; i++) // просматриваем все вершины
      if (a[i][end] != 0)   // если связь есть
      {
        int temp = weight - a[i][end]; // определяем вес пути из предыдущей вершины
        if (temp == d[i]) // если вес совпал с рассчитанным
        {                 // значит из этой вершины и был переход
          weight = temp; // сохраняем новый вес
          end = i;       // сохраняем предыдущую вершину
          ver[k] = i + 1; // и записываем ее в массив
          k++;
        }
      }
  }
  // Вывод пути (начальная вершина оказалась в конце массива из k элементов)
  printf("\nВывод кратчайшего пути\n");
  for (int i = k - 1; i >= 0; i--)
    printf("%3d ", ver[i]);
  getchar(); getchar();
  return 0;
}

Результат выполнения
Алгоритм Дейкстры


Назад: Алгоритмизация

Комментариев к записи: 125

  • У меня вопрос по реализации алгоритма. В описании задачи указано что данный алгоритм подходит для нахождения кратчайшего пути в сетях, где есть одностороннее движение. Но при инициализации матрицы связей for (int i = 0; i<SIZE; i++) { a[i][i] = 0; for (int j = i + 1; j<SIZE; j++) { printf("Введите расстояние %d - %d: ", i + 1, j + 1); scanf("%d", &temp); a[i][j] = temp; a[j][i] = temp; } } Отсутствует возможность указать что есть дорога из a[i][j] в a[j][i], но дороги из a[j][i] в a[i][j] нет. Получается что данное реализация уже на этапе инициализации предусмотрена только для неориентированных сетей.

    • Елена Вставская
      Инициализация взята для примера. В случае ориентированного графа нужно задать все расстояния, а не только верхний треугольник матрицы (с дублированием в нижний)

  • Дмитрий
    Добрый день! Хотел бы обратить внимание, что в объяснении алгоритма у Вас в одном месте неправильно выставлены знаки препинания, и это изменяет смысл фразы. Может сбить с толку человека, который впервые знакомится с решением через данный текст. Вот отрывок второго абзаца пункта "Первый шаг: "Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1, значению её метки, и длины ребра, идущего из 1-й в 2-ю..." Здесь по вашей записи "значение её метки" - получается как второе слагаемое из трех. А на самом деле это просто уточнение насчёт первого и слагаемых всего 2: расстояние до вершины 1 и длина ребра. Поэтому рекомендую поставить вместо запятых скобки, и всё сразу станет понятно: "Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1 (значению её метки), и длины ребра, идущего из 1-й в 2-ю..." А вообще, замечательная статья. Спасибо Вам!

    • Дмитрий
      Да, сам лишнюю запятую поставил от спешки) Извиняюсь. Должно быть так: "Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1 (значению её метки) и длины ребра, идущего из 1-й в 2-ю..."

  • Здравствуйте, я переделала код через функции, помогите пожалуйста, как в его можно изменить для ориентированного то есть все поже самое, но идти можно только в одну сторону я еще новичок, можно подробно, пожалуйста
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    #define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #define SIZE 6// количество вершин в нашем графе
    int matrix[SIZE][SIZE] = { 0 }; // матрица связей
    int a[SIZE]; // посещенные вершины
    int d[SIZE]; // минимальное расстояние
    int save;//временное хранение различных величин
    int begin_index = 0;//задаем индекс начальной вершины, от которой будем искать путь
    int min;
    int minindex;

    void matrix_svyazey()
    {
        for (int i = 0; i < SIZE; i++)
        {
            matrix[i][i] = 0;
            for (int j = i + 1; j < SIZE; j++) {
                printf("vvedite rasstoyanie %d - %d: ", i + 1, j + 1);
                scanf("%d", &save);
                matrix[i][j] = save;
                matrix[j][i] = save;
            }
        }
    }

    void Vyvod_matrix()
    {
        for (int i = 0; i < SIZE; i++)
        {
            for (int j = 0; j < SIZE; j++)
                printf("%5d ", matrix[i][j]);
            printf("\n");
        }
    }

    void alg_kratchayshego_pyti()
    {

        for (int i = 0; i < SIZE; i++)
        {
            d[i] = 10000;
            a[i] = 1;//отмечает все вершины как необработанные.
        }
        d[begin_index] = 0;
        // Шаг алгоритма
        do {
            minindex = 10000;//индекс вершины с минимальным весом
            min = 10000;// мин вес
            for (int i = 0; i < SIZE; i++)
            { // Если вершину ещё не обошли и вес меньше min
                if ((a[i] == 1) && (d[i] < min))
                { // Переприсваиваем значения
                    min = d[i];
                    minindex = i;
                }
            }
            // Добавляем найденный минимальный вес
            // к текущему весу вершины
            // и сравниваем с текущим минимальным весом вершины
            if (minindex != 10000)
            {
                for (int i = 0; i < SIZE; i++)
                {
                    if (matrix[minindex][i] > 0)
                    {
                        save = min + matrix[minindex][i];
                        if (save < d[i])
                        {
                            d[i] = save;
                        }
                    }
                }
                a[minindex] = 0;
            }
        } while (minindex < 10000);
        
    }

    void v_p()
    {
        int ver[SIZE]; // массив посещенных вершин
        int end = 5; // индекс конечной вершины = 6 - 1
        ver[0] = end + 1; // начальный элемент - конечная вершина
        int k = 1; // индекс предыдущей вершины
        int weight = d[end]; // вес конечной вершины

        while (end != begin_index) // пока не дошли до начальной вершины
        {
            for (int i = 0; i < SIZE; i++) // просматриваем все вершины
                if (matrix[end][i] != 0)   // если связь есть
                {
                    int temp = weight - matrix[end][i]; // определяем вес пути из предыдущей вершины
                    if (temp == d[i]) // если вес совпал с рассчитанным
                    {                 // значит из этой вершины и был переход
                        weight = temp; // сохраняем новый вес
                        end = i;       // сохраняем предыдущую вершину
                        ver[k] = i + 1; // и записываем ее в массив
                        k++;
                    }
                }
        }
        // Вывод кратчайших расстояний до вершин
        printf("\nkratchayshee rasstoyanie do vershin \n");
        for (int i = 0; i < SIZE; i++)
            printf("%5d ", d[i]);
        // Вывод пути (начальная вершина оказалась в конце массива из k элементов)
        printf("\nVyvod kratchayshego pyti\n");
        for (int i = k - 1; i >= 0; i--)
            printf("%3d ", ver[i]);
    }
    int main()
    {
      
        // Инициализация матрицы связей
        matrix_svyazey();

        // Вывод матрицы связей
        Vyvod_matrix();

        alg_kratchayshego_pyti();
        // Восстановление пути
        v_p();
       
        getchar();
        getchar();
        return 0;
    }


      • я заменила a[size][size] на a[size][size]={0} набрала строчку а[j][i] = temp;но у меня теперь вообще но показывается в консоли вывод кратчайшего пути

      • Елена Вставская
        Я вручную форматирую программу при одобрении комментариев.

    • Елена Вставская
      На сайте предложен код, который работает и с ориентированным, и с неориентированный графом

      • получается ребро 12 можно обозначить, а ребро 21 никак нельзя, хотя в графе как раз например нужен путь именно из 21, как сделать так, чтобы можно было отметить все пути? я пробовала в 18 строчке for (int j = i + 1; j<SIZE; j++) { сделать int j = 0; j<SIZE; j+ но тогда в кратчайшем пути появляется первая и последняя вершины

        • Елена Вставская
          1
          2
          3
          4
          5
          6
          7
          8
          9
          for (int i = 0; i < SIZE; i++)
          {
          matrix[i][i] = 0;
          for (int j = 0; j < SIZE; j++) {
          printf("vvedite rasstoyanie %d - %d: ", i + 1, j + 1);
          scanf("%d", &save);
          matrix[i][j] = save;
          }
          }

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

          • Елена Вставская
            А можно данные, для которых кратчайший путь не выводится?

          • какие бы числа я не вводила с клавиатуры при этой программе выводится матрица,кратчайшее расстояние до вершин и все
            1
            2
            3
            4
            5
            6
            7
            8
            9
            10
            11
            12
            13
            14
            15
            16
            17
            18
            19
            20
            21
            22
            23
            24
            25
            26
            27
            28
            29
            30
            31
            32
            33
            34
            35
            36
            37
            38
            39
            40
            41
            42
            43
            44
            45
            46
            47
            48
            49
            50
            51
            52
            53
            54
            55
            56
            57
            58
            59
            60
            61
            62
            63
            64
            65
            66
            67
            68
            69
            70
            71
            72
            73
            74
            75
            76
            77
            78
            79
            80
            81
            82
            83
            84
            85
            86
            87
            88
            89
            90
            91
            92
            93
            94
            95
            96
            97
            98
            99
            100
            101
            102
            103
            104
            105
            106
            107
            108
            109
            110
            111
            112
            113
            114
            115
            116
            117
            118
            119
            120
            121
            122
            123
            int matrix[SIZE][SIZE]; // матрица связей
            int a[SIZE]; // массив посещенных вершинн
            int d[SIZE]; // минимальное расстояние
            int save;//переменная для временного хранения величин
            int begin_index = 0;//задаем индекс начальной вершины, от которой будем искать путь
            int min;
            int minindex;

            void matrix_svyazey()
            {
              for (int i = 0; i < SIZE; i++)
              {
                matrix[i][i] = 0;
                for (int j = 0; j < SIZE; j++) {
                  printf("vvedite rasstoyanie %d - %d: ", i + 1, j + 1);
                  scanf("%d", &save);
                  matrix[i][j] = save;    
                }
              }
            }

            void Vyvod_matrix()
            {
              for (int i = 0; i < SIZE; i++)
              {
                for (int j = 0; j < SIZE; j++)
                  printf("%5d ", matrix[i][j]);
                printf("\n");
              }
            }

            void alg_kratchayshego_pyti()
            {

              for (int i = 0; i < SIZE; i++)
              {
                d[i] = 10000;
                a[i] = 1;//отмечает все вершины как необработанные
                //printf("%d %5d", d[i], a[i]);
              }
              d[begin_index] = 0;
              // алгоритм
              do {
                minindex = 10000;//индекс вершины с минимальным весом
                min = 10000;// мин вес
                for (int i = 0; i < SIZE; i++)
                { 
                  if ((a[i] == 1) && (d[i] < min))
                  { 
                    min = d[i];
                    minindex = i;
                  }
                }
                // добавляем найденный минимальный вес к текущему весу вершины и сравниваем с текущим минимальным
                
                if (minindex != 10000)
                {
                  for (int i = 0; i < SIZE; i++)
                  {
                    if (matrix[minindex][i] > 0)
                    {
                      save = min + matrix[minindex][i];
                      if (save < d[i])
                      {
                        d[i] = save;
                      }
                    }
                  }
                  a[minindex] = 0;
                }
              } while (minindex < 10000);

            }

            void v_p()
            {
              int ver[SIZE]; // массив посещенных вершин
              int end = 5; // индекс последней вершины = 6 - 1
              ver[0] = end + 1; // начальный элемент - последняя вершина
              int k = 1; // индекс предыдущей вершины
              int weight = d[end]; // вес последней вершины

              while (end != begin_index) // пока не дошли до начальной вершины
              {
                for (int i = 0; i < SIZE; i++) 
                  if (matrix[end][i] != 0) 
                  {
                    int temp = weight - matrix[end][i]; // вес пути из предыдущей вершины
                    if (temp == d[i]) 
                    { 
                      weight = temp; 
                      end = i; // сохраняем предыдущую вершину
                      ver[k] = i + 1; // записываем ее в массив
                      k++;
                    }
                  }
              }
              
              printf("\n\nkratchayshee rasstoyanie do vershin \n");
              for (int i = 0; i < SIZE; i++)
                printf("%5d ", d[i]);
              // Вывод пути (начальная вершина оказалась в конце массива из k элементов)
              printf("\nVyvod kratchayshego pyti\n");
              for (int i = k - 1; i >= 0; i--)
                printf("%3d ", ver[i]);
            }
            int main()
            {

              
              matrix_svyazey();

              // Вывод матрицы связей
              Vyvod_matrix();

              alg_kratchayshego_pyti();
              // Восстановление пути
              v_p();

              getchar();
              getchar();
              return 0;
            }

          • Елена Вставская
            Ошибка в строчках 86, 88.
            1
            2
            3
            4
            5
            6
            7
            8
            9
            10
            11
            12
            13
            14
            15
            while (end != begin_index) // пока не дошли до начальной вершины
              {
                for (int i = 0; i < SIZE; i++)
                  if (matrix[i][end] != 0)
                  {
                    int temp = weight - matrix[i][end]; // вес пути из предыдущей вершины
                    if (temp == d[i])
                    {
                      weight = temp;
                      end = i; // сохраняем предыдущую вершину
                      ver[k] = i + 1; // записываем ее в массив
                      k++;
                    }
                  }
              }

  • Добрый день. По заданию нужно найти самый длинный путь, я попытался переделать алгорим Дейкстры. Но, он не работает. Помогите найти ошибку, если возможно сделать задание по этому алгоритму. Если не возможно, то подскажите как сделать.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    #define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #define SIZE 8
    int main()
    {
        int a[SIZE][SIZE]=
        {
    {0, 0, 14, 0, 0, 21, 0, 0},
    {13, 0, 15, 0, 0, 0, 0, 14},
    {14, 15, 0, 12, 0, 0, 13, 0},
    {0, 0, 0, 0, 8, 0, 0, 0},
    {0, 0, 0, 8, 0, 0, 13, 0},
    {21, 0, 0, 0, 5, 0, 0, 0},
    {0, 0, 0, 0, 13, 0, 0, 16},
    {0, 0, 0, 0, 0, 0, 16, 0},
        };
         // матрица связей
        int d[SIZE]; // минимальное расстояние
        int v[SIZE]; // посещенные вершины
        int temp, minindex, min;
        int begin_index = 0;
        system("chcp 1251");
        system("cls");
        // Инициализация матрицы связей
        /*for (int i = 0; i < SIZE; i++)
        {
            a[i][i] = 0;
            for (int j = 0; j < SIZE; j++) {
                printf("Введите расстояние %d - %d: ", i + 1, j + 1);
                scanf("%d", &temp);
                a[i][j] = temp;
                
            }
        }*/

        // Вывод матрицы связей
        for (int i = 0; i < SIZE; i++)
        {
            for (int j = 0; j < SIZE; j++)
                printf("%5d ", a[i][j]);
            printf("\n");
        }
        //Инициализация вершин и расстояний
        for (int i = 0; i < SIZE; i++)
        {
            d[i] = 0;
            v[i] = 1;
        }
        d[begin_index] = 0;
        // Шаг алгоритма
        do {
            minindex = -1;
            min = -1000;
            for (int i = 0; i < SIZE; i++)
            { // Если вершину ещё не обошли и вес меньше min
                if ((v[i] == 1) && (d[i] > min))
                { // Переприсваиваем значения
                    min = d[i];
                    minindex = i;
                }
            }
            // Добавляем найденный минимальный вес
            // к текущему весу вершины
            // и сравниваем с текущим минимальным весом вершины
            if (minindex !=-1 )
            {
                for (int i = 0; i < SIZE; i++)
                {
                    if (a[minindex][i] > 0)
                    {
                        temp = min + a[minindex][i];
                        if (temp > d[i])
                        {
                            d[i] = temp;
                        }
                    }
                }
                v[minindex] = 0;
            }
        } while (minindex > -1);
        // Вывод кратчайших расстояний до вершин
        printf("\nСамое длинное расстояние до вершины: \n");
        for (int i = 0; i < SIZE; i++)
            printf("%5d ", d[i]);

        // Восстановление пути
        int ver[SIZE]; // массив посещенных вершин
        int end = 3; // индекс конечной вершины = 5 - 1
        ver[0] = end + 1; // начальный элемент - конечная вершина
        int k = 1; // индекс предыдущей вершины
        int weight = d[end]; // вес конечной вершины

        while (end != begin_index) // пока не дошли до начальной вершины
        {
            for (int i = 0; i < SIZE; i++) // просматриваем все вершины
                if (a[i][end] != 0)   // если связь есть
                {
                    int temp = weight - a[i][end]; // определяем вес пути из предыдущей вершины
                    if (temp == d[i]) // если вес совпал с рассчитанным
                    {                 // значит из этой вершины и был переход
                        weight = temp; // сохраняем новый вес
                        end = i;       // сохраняем предыдущую вершину
                        ver[k] = i + 1; // и записываем ее в массив
                        k++;
                    }
                }
        }
        // Вывод пути (начальная вершина оказалась в конце массива из k элементов)
        printf("\nВывод самого длинного пути\n");
        for (int i = k - 1; i >= 0; i--)
            printf("%3d ", ver[i]);
        getchar(); getchar();
        return 0;
    }

    • Елена Вставская
      Задача не имеет однозначного решения, потому что, перемещаясь по одной и той же дуге графа многократно, можно увеличивать путь до бесконечности.

  • Алексей
    А поиск в одну сторону не работает? Например если визуально граф выглядит как дерево, что бы снизу вверх можно было пройти, а сверху вниз нет? Вот такой вариант не работает:
    1
    2
    3
    4
    5
    6
    7
    {0, 1, 1, 0, 0, 0, 0},
    {0, 0, 0, 1, 1, 0, 0},
    {0, 0, 0, 0, 0, 1, 1 },
    {0, 0, 0, 0, 0, 0, 0 },
    {0, 0, 0, 0, 0, 0, 0 },
    {0, 0, 0, 0, 0, 0, 0 },
    {0, 0, 0, 0, 0, 0, 0 }
    А такой работает:
    1
    2
    3
    4
    5
    6
    7
    {0, 1, 1, 0, 0, 0, 0},
    {1, 0, 0, 1, 1, 0, 0},
    {1, 0, 0, 0, 0, 1, 1 },
    {0, 1, 0, 0, 0, 0, 0 },
    {0, 1, 0, 0, 0, 0, 0 },
    {0, 0, 1, 0, 0, 0, 0 },
    {0, 0, 1, 0, 0, 0, 0 }
    Спасибо если ответите :)

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

      • Алексей
        Не знаю как тут форматировать текст, попробую так, если не получится, то не пинайте сильно :) Вобщем, ковырял ковырял, так ничего и не получилось, вычислил что зависает где-то в цикле восстановления пути. Даже банально в графе из трёх точек, не может найти путь
        1
        2
        3
        {0, 1, 1 },
        {0, 0, 0 },
        {0, 0, 0 }
        Странно, очень странно...


          • Алексей
            Как от 0 до 1 и 2 не работает, так и от 1 и 2 до 0.
            1
            2
            3
            {0, 1, 1 },
            {1, 0, 0 },
            {1, 0, 0 }
            А вот так всё работает. Пробовал вместо единичек разные значения ставить, тоже в каких-то случаях не проходил до конца.

          • Елена Вставская
            Исправила ошибку в статье. Теперь будет работать восстановление пути и для ориентированных графов.

  • Даниэль
    Получается вершины если в графическом виде представлять, начинаются с 0 и рассчитывается тоже с 0;

    • Валерий
      Здравствуйте, не совсем понял, почему индекс конечной вершины end изначально равен 4, ведь вершин 6, то есть end должен равняться 5.

      • Елена Вставская
        Потому что мы решили искать кратчайший путь до 5 вершины. Можем искать до любой.

  • Здравствуйте, Елена. Очень доступно вы обяснили алгоритм Дейкстры. Спасибо огромное! У меня к вам просьба. Может быть вы обясните мне как решить следующую задачу. Есть масив отрезков прямых линий.Отрезки не пересекаются. Если соприкасаются, то только в начале или конце отрезка.Также может существовать несколько идентичных отрезков, накладываемых друг на друга. Необходимо упорядочить их так, чтобы можно было сделать трассировку по всем отрезкам, в том числе и по идентичным - без пропусков. Если это невозможно, тогда найти наибольшее количество отрезков соединенных между собой. Спасибо.

    • Елена Вставская
      А идентичные отрезки учитываются как один или каждый сам за себя?

      • Нет. Это не один и тот же отрезок. По нему тоже необходимо сделать трассировку.

        • Елена Вставская
          Представьте свой массив отрезков в виде графа, где координаты начала и конца - вершины, а сами отрезки - ребра.
          А дальше воспользуйтесь алгоритмом поиска в глубину. Правда, придется его проводить циклически, чтоб найти все пути.

          • Спасибо за ответ. Но это будет очень трудоемкий процесс. Ведь поиск нужно проводить с каждой отдельной вершины. А отрезков может быть и 100000 и больше. Может быть есть другое решение?

  • Простите, а как сделать так чтобы выводилась последовательность вершин, определяющая кратчайший путь не до фиксированный вершины, а до всех вершин?

    • Елена Вставская
      В строке 77 назначить нужную вершину и повторить восстановление пути требуемое число раз.

      • А зачем в 77 строке назначать вершину? Там же конечная вершина( та до, которой нужно найти путь), а мне нужно до всех вершин графа

  • Здравствуйте, а где прописано, что начальная вершина это 1 и можно ли сделать так, чтобы пользователь сам выбирал начальную вершину?


      • Екатерина
        Здравствуйте! Если в begin_index для указанного примера поместить значение 4 (то есть, в качестве начальной вершины взять вершину 5) то путь до вершины 1 рассчитывается неверно, точнее, выводится не самый кратчайший. Подскажите, пожалуйста, с чем это связано.

  • Валерий Альбертович
    Как именно можно из этого алгоритма сделать поиск наибольшего пути? В каком месте кода и что именно изменить?

    • Елена Вставская
      Начальные значения вместо 10000 взять 0 и поменять условие < на > в 45 строке

  • Как можно найти кратчайший путь до точки я понял, а вот про критический путь ничего не сказано. Как можно найти критический путь?

    • Александр
      Кратчайший-это и есть критический. Коллеги, а можно ли как-то модифицировать чтобы вывести все пути между двумя заданными вершинами (то есть не только критический путь, а так же остальные), ну или между всеми вершинами графа.

  • Два онлайн компилятора ошибки находят https://www.onlinegdb.com/online_c++_compiler http://cpp.sh/ main.cpp: In function ‘int main()’: main.cpp:77:11: error: storage size of ‘ver’ isn’t known int ver[]; // массив посещенных вершин ^ main.cpp:81:16: error: ‘dist’ was not declared in this scope int weight = dist[end]; // вес конечной вершины ^ main.cpp:82:1: error: ‘var’ was not declared in this scope var arr =[] ^

    • Елена Вставская
      Пока ничего удивительного не вижу. int ver[]; не указан размер массива
      int weight = dist[end] - нужен полный код, чтобы увидеть, где присвоены значения элементов массива dist
      var arr=[] - синтаксически некорректная строка

    • Как сделать, чтобы пользователь вводил точку графа и до неё считался кратчайший путь? В статье от 1 и до следующей, а так надо чтобы в консоле вводит пользователь например 4 и вводил координаты до 4 точки, чтобы она была началом, но чтобы не в коде сам менял, а через консоль



  • Здравствуйте, в вашем алгоритме реализованы кратчайшие пути от первой вершины до всех остальных,т.е. от первой до первой , от первой до второй, от первой до третьей,от первой до четвертой и от первой до пятой , а как сделать так,чтобы находило автоматически для всех вершин пести до всех остальных, например , кратчайшие пути от второй вершины до первой,второй,третьей, и т.д., потом кратчайшие пути от третьей до первой ,второй ,третьей и т.д. , и так до пятой вершины , чтобы как бы создать матрицу расстояний

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


        • Елена Вставская
          В код примера внесла поправки. Теперь номер начальной вершины задается в строке 11.

  • Я ознакомился с комментариями выше, сделать ориентированный граф вышло, но вот вывести путь кратчайший до той вершины, которая дана по условию задания у меня не вышло. Вам будет трудно оставить код по выводу кратчайшего пути от одной заданной вершины до другой? Также интересен следующий вопрос.. если я хочу от условно 2 вершины до 5, узнать кратчайший путь и длину, то надо менять в 38 строке элемент по индексу 3, присваивая его 0?

    • Елена Вставская
      Нужно перед поиском кратчайшего пути поменять местами вершины графа в матрице так, чтобы отправная вершина 2 оказалась начальной.

  • Здравствуйте, не могли бы Вы подсказать, как сделать так, чтобы размер матрицы задавался пользователем в консоли?

  • Здравствуйте, как сильно нужно изменить алгоритм, чтобы он работал для ориентированного взвешенного графа? Ведь если пытаться использовать именно этот алгоритм, то в определённых ориентированных графах будет ответ, как будто он неориентированный, т.е другой.

  • Здравствуйте. Я не понимаю такой момент. Ведь мы сначала присваиваем бесконечно большой вес всем вершинам. Зачем мы потом опять присваиваем бесконечно большое число minindex и min?

    • Елена Вставская
      А как иначе делать первое сравнение в 45 строке? Эти переменные должны уже иметь какое-то значение.

  • Глеб Графа
    1
    2
    3
    4
    5
    6
    7
    8
    for (int i = 0; i<SIZE; i++)
        { // Если вершину ещё не обошли и вес меньше min
          if ((v[i] == 1) && (d[i]<min))
          { // Переприсваиваем значения
            min = d[i];
            minindex = i;
          }
        }
    Как это работает если min у нас 10000 и все d[i]=10000, условие же не сработает

  • Здравствуйте! А как найти длину максимального пути и сам путь? Есть ли алгоритм?

  • Николай
    Здравствуйте! Правильно ли я понимаю, что данный алгоритм предназначен для поиска кратчайших путей от известной вершины до ВСЕХ? А какой алгоритм выбрать, если нужно найти кратчайший путь между двумя данными вершинами? Подойдет ли тут, например, волновой алгоритм? Заранее спасибо!

    • Елена Вставская
      Можете использовать этот же алгоритм, и прекратить поиск как только достигнете требуемой вершины

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

        • Елена Вставская
          Думаю, да. Здесь есть описание волнового алгоритма, но для невзвешенного графа https://prog-cpp.ru/data-graph/

  • Дмитрий
    Приветствую, меняется ли алгоритм существенно, если весы будут принимать отрицательные значения

    • Елена Вставская
      Зависит от условия задачи, допускается ли отрицательная длина пути.

  • Здравствуйте. Я убрал 22-ую строку, чтобы граф стал ориентированным, но при этом перестал выводиться кратчайший путь. Что нужно еще изменить в коде чтобы он выводился?


      • Немного неточно выразился. Мне нужно, что всё было как в этом коде за исключением симметричности. То есть ввожу всё так же, но чтобы всё, что ниже нулевой диагонали, тоже было равно нулю. Заранее спасибо

        • Елена Вставская
          Тогда нужно исходно обнулить все элементы массива а. Строка 7:
          1
          int a[SIZE][SIZE]={0};

  • "int k = 1; // индекс предыдущей вершины" Подскажите пожалуйста, предыдущая вершина это какая?


  • Евгений
    Уважаемая Елена, спасибо за данную статью и вообще за Вашу просветительскую работу в направлении компьютерных наук! В России эта сфера всегда будет испытывать дефицит в методических материалах на русском языке, равно как и в специалистах, способных создавать качественное ПО. Касательно самой статьи - как Вы считаете, имеет ли смысл несколько изменить программный код таким образом, чтобы граф создавался автоматически случайным образом? Что-то типа:
    1
    2
    3
    4
    5
    6
    7
    bool** graph;
    srand(time(0));
    graph = new bool* [size];
    for(int i=0; i<size; i++)
     for(int j=0; j,size; j++)
      if(i==j) graph[i][j] = false;
       else graph[i][j] = graph[j][i] = (prob() < 0.19);//for density = 0.19
    Спасибо.

  • Здравствуйте. Это единственная статья про алгоритм Дейкстры? Меня интересует алгоритм Дейкстры, реализованный на основе d-кучи. В поиске на текущем сайте не нашёл.


    • Елена Вставская
      Используется для временного хранения различных величин внутри циклов


        • Елена Вставская
          Исходное всем вершинам присваивается бесконечно большой вес (массив d), чтобы потом этот вес уточнять. Массив v отмечает все вершины как необработанные.

  • Шурик З.
    Спасибо большое, с помощью статьи смог объяснить студентам, как правильно делать.


    • Елена Вставская
      min - это минимальный вес, а minindex - индекс вершины с минимальным весом

  • Добрый день, появился еще вопрос. Вот большой цикл, который на строчках 40-67, как его можно заменить его условие при измене этого цикла на эквивалентный ему while () { ... }? Ибо, если так и оставить (minindex<10000), компилятор ведь даже не зайдет в цикл. Подскажите, пожалуйста.

    • Елена Вставская
      Не поняла вопроса. А чем цикл с постусловием do...while не устроил? Да, цикл while() может не выполниться ни разу. Для этого и используется цикл с постусловием.

  • Елена, извините, немного не понятно с конечным выводом. Для чего мы снова выводим матрицу связей? Разве мы не должны вывести кратчайшее расстояние? Заранее спасибо за ответ!

    • Елена Вставская
      Спасибо за замечание. Действительно, мы выводим вектор полученных кратчайших расстояний до вершин. Ошиблась в комментарии.


  • Анатолий
    А вы не подскажите как поступить с ориентированым графом? Как при это меняется матрица?

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

  • Анатолий
    То есть SIZE регулирует до какой вершины я хочу добраться? Допустим, если из 1й вершины в 3-ю, то вместо SIZE я должен поставить 3?

    • Елена Вставская
      Нет, SIZE - это количество вершин графа. А кратчайшие пути до всех вершин (из первой) по завершении алгоритма формируются в массиве d. Если нас в качестве исходной интересует другая вершина, то мы всегда можем поменять строки и столбцы матрицы так, чтобы исходная вершина оказалась на первом месте.

  • Анатолий
    Вы не так меня поняли. Меня интересует как самому выбрать от какой вершины и до какой я хочу найти минимальное расстояние и вывести эти вершины

    • Елена Вставская
      Сам алгоритм - это строки с 37 по 67 примера. При желании Вы можете его вынести в отдельный метод. В результате формируется вектор d, который содержит кратчайшие пути до всех вершин из первой рассматриваемой вершины. А матрицу, в которой Вы ищете кратчайший путь, Вы задаёте сами.

  • Анатолий
    Вы могли бы приложить код, просто еще только начал работать то стеком и не совсем разбираюсь. Буду очень благодарен

  • Дмитрий
    Как программным путём вывести путь(то есть через какие вершины нужно идти от 1-2, 1-3 и т.д.). Допустим от 1 до 4, можно пойти через 2 и 3 как вывести в коде что бы показать что мы пошли именно через 2 вершину?

    • Елена Вставская
      При обходе графа необходимо создать стек, куда помещать все "пройденные" рёбра в виде структуры "начало-конец". После того, как требуемая вершина достигнута, извлекаем из стека последнее ребро (с концом в этой вершине) и переходим к началу этого ребра и сохраняем эту вершину. Теперь, последовательно извлекая из стека рёбра, необходимо определить, как мы попали в эту сохранённую вершину. И так далее, пока не дойдём до начала. Таким образом, мы получим весь найденный путь, но от конца к началу. Если необходим путь от начала к концу, то нужно воспользоваться еще одним стеком.


  • Дмитрий
    Здравствуйте, подскажите, пожалуйста, а как реализовать в коде, чтобы можно было вводить количество вершин? Заранее благодарю

  • я не это имел в виду, а то как по алгоритму сделать вывод о выборе пути. Например чтобы из 1 попасть в пятую нужно мысленно встать в пятую вершину и идти к той у который минимальный вес. Таким образом получаем 5-6-3-1. Следовательно наш искомый путь 1-3-6-5. Я пропустил один пункт в объяснении но поскольку я не уверен что вообще прав дождусь вашего ответа

    • Елена Вставская
      Совершенно верно. Путь ищется в обратном направлении, то есть в вершину 5 мы попали из вершины 6. Здесь только критерий - не минимальный вес предыдущей вершины, а минимальный вес суммы предыдущей вершины и дуги к текущей. То есть в данном случае из вершины 5 мы выбираем обратный путь как min(11+9, 20+6).

  • Забыли описать самое главное. А как определить через какие вершины идти минимальным путем, например, из первой в пятую. Объясните пожалуйста

  • Для хранения весов графа используется квадратная матрица расшифруйте матрицу.


    • Елена Вставская
      Это для того, чтобы русскоязычные символы корректно отображались в окне консоли. system("chcp 1251"); // изменение кодовой страницы на 1251 system("cls"); // очистка экрана

  • В википедии при разрисовке данного графа содержится ошибка, каким образом на 4-м шаге, из 6-й посещенной вершины, мы попадаем в 4-ю? Да, вес у вершин 4 и 5 одинаковый, но это противоречит физическому смыслу, если представить, что вы находитесь на развилке дорог. Порядок вершин должен быть по идее ... 6, 5, 4.

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



Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *