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

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

 

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

Для решения указанной задачи можно использовать алгоритм Дейкстры — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 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;
  int minindex, min;
  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[0] = 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 > 0) // пока не дошли до начальной вершины
  {
    for(int i=0; i<SIZE; i++) // просматриваем все вершины
      if (a[end][i] != 0)   // если связь есть
      {
        int temp = weight - a[end][i]; // определяем вес пути из предыдущей вершины
        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;
}

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


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

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



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

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


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

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

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

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

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

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


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

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

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

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

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

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

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

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

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


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

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

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

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


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

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


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


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

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

  • Евгений
    Уважаемая Елена, спасибо за данную статью и вообще за Вашу просветительскую работу в направлении компьютерных наук! В России эта сфера всегда будет испытывать дефицит в методических материалах на русском языке, равно как и в специалистах, способных создавать качественное ПО. Касательно самой статьи - как Вы считаете, имеет ли смысл несколько изменить программный код таким образом, чтобы граф создавался автоматически случайным образом? Что-то типа:
    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
    Спасибо.


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

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


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

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

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

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

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

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

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

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

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

  • Глеб Графа
    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, условие же не сработает

    • Елена Вставская
      Исходно значение min выбирается больше всех вычисленных с тем, чтобы заменить его на меньшие значения в цикле.

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

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

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

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

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

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

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

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