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

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

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

Для решения указанной задачи можно использовать алгоритм Дейкстры - алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 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.

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

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

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
#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++) {
      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);
  // Вывод матрицы связей
  for(int i=0;i<SIZE;i++)
    printf("%5d \n",d[i]);
  getchar(); getchar();
}

Результат выполнения
Результат выполнения
Назад


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

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

  • я не это имел в виду, а то как по алгоритму сделать вывод о выборе пути. Например чтобы из 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 не будет опубликован. Обязательные поля помечены *