Алгоритм Дейсктры: C++, Python Пример кода

Каков кратчайший путь или кратчайшее расстояние?

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

Здесь «Стоимость» означает количество узлов в маршруте или сумму затрат на каждом пути. Путь может иметь одно или несколько ребер. Соединение между двумя вершинами называется «ребро». Существуют различные типы алгоритмов кратчайшего пути, такие как алгоритм Дейкстры, алгоритм Беллмана-Форда и т. д.

Здесь мы обсуждаем алгоритм Дейкстры.

Давайте посмотрим на следующий взвешенный график:

Термин «Взвешенный» означает перемещение затрат с одного узла на другой. Например, при переходе от узла 1 к узлу 2 стоимость или вес равны 1.
Путь между узлами 1 и 2 называется ребром.
«Ненаправленный» означает, что вы можете переместить один узел на другой и вернуться к предыдущему узлу. Итак, если мы попытаемся найти все маршруты от узла 1 до узла 7, то это будет:

Маршрут или путь	Цена
1-2-6-7	(1+3+3) = 7
1-2-3-7	(1+9+1) = 11
1-3-7	(7+1) = 8
1-4-5-7	(6+2+5) = 13

Среди этих четырех маршрутов мы видим, что первый маршрут будет стоить нам 7. Таким образом, это самый короткий путь с точки зрения стоимости.

Как работает алгоритм Дейкстры

Алгоритм Дейкстры может найти кратчайшее расстояние как в ориентированных, так и в неориентированных взвешенных графах. Этот алгоритм является жадным, поскольку он всегда выбирает самый короткий или ближайший узел из начала координат. Термин «жадный» означает, что среди множества исходов или результатов алгоритм выберет лучший из них.

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

В разделе «пример» ниже вы увидите пошаговый подход. Это работает следующим образом:

Шаг 1) Инициализируйте начальный узел с нулевой стоимостью, а остальную часть узла — с бесконечной стоимостью.
Шаг 2) Поддерживайте массив или список для отслеживания посещенных узлов.
Шаг 3) Обновите стоимость узла, указав минимальную стоимость. Это можно сделать путем сравнения текущей стоимости со стоимостью пути. (Демонстрация показана в разделе примеров)
Шаг 4) Продолжайте шаг 3, пока не будут посещены все узлы.

Выполнив все эти действия, мы найдем путь от источника к месту назначения, который стоит минимум.

Разница между Дейкстрой и BFS, DFS

Основное различие между Дейкстрой и BFS-DFS заключается в том, что Дейкстра — это алгоритм поиска кратчайшего пути, а BFS, DFS — алгоритм поиска пути. В общих случаях BFS и DFS не учитывают стоимость при поиске пути. Таким образом, эти алгоритмы не могут гарантировать кратчайший путь.

2D-сетка, демонстрирующая, как работает BFS

Демонстрация 2D-сетки — Алгоскетч, показывает демонстрацию BFS

Эта демонстрация показывает, что BFS только находит путь. Однако его не волнует вес пути. БФС (Поиск в ширину) предполагает, что путешествие от одного узла к другому будет стоить всего 1.

Но давайте посмотрим пример графика:

Здесь он находит путь на уровне 2. BFS обходит граф в порядке уровней. Итак, он путешествует так:

Шаг 1) Начните с узла «1» и посетите все соседние узлы 2,3,4.

Шаг 2) Отметьте узел 2,3,4 как уровень 1 и посетите соседние узлы. Он продолжит исследовать все соседние узлы, пока не достигнет узла назначения.

С точки зрения DFS, он будет проходить путь от 1 до 7 следующим образом:

1→2→3→7 (исходная стоимость 10, стоимость DFS 3)
1→2→6→7 (исходная стоимость 7, стоимость DFS 3)
1→3→7 (исходная стоимость 8, стоимость DFS 2)
1→4→5→7 (исходная стоимость 13, стоимость DFS 3)

Как мы видим, DFS вычисляет стоимость пути с учетом глубины или количества ребер.

DFS делает следующее:

DFS может найти путь от источника (начальной вершины) до пункта назначения.
Он не может гарантировать, является ли обнаруженный путь от исходного узла до места назначения кратчайшим путем или нет.

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

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

Алгоритм Дейкстры использует стоимость или вес для расчета общей стоимости пути.

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

Алгоритм Дейкстры находит кратчайшие пути путем вычисления весов. Он не будет искать все возможные пути. Продемонстрируем алгоритм Дейкстры на примере. Например, вас попросили найти кратчайший путь от узла 1 до узла 7.

Ниже приведены шаги для этого процесса:

Шаг 1) Инициализируйте стоимость начального узла равной 0.

Оставшуюся часть узла назначьте «Инф». Это означает, что между начальной вершиной (источником) и узлом не существует пути или путь еще не посещен.

Шаг 2) Когда вы выберете узел 1, он будет помечен как посещенный. Затем обновите всех соседних соседей узла 1. 2,3,4 — соседние узлы узла 1.

При обновлении стоимости нам необходимо следовать следующей процедуре:

Мы можем обновить стоимость каждого узла, используя приведенную выше формулу. Например, мы находились в узле 1, и нам нужно было обновить стоимость соседнего узла 2,3,4.

После обновления стоимость или вес будут выглядеть так:

Шаг 3) Для узла «2» соседи — 6 и 3. Мы обновляем стоимость на «6», сравнивая бесконечность (текущее значение). Стоимость узла 2 + стоимость пути от 2 до 6. Проще говоря, узел «6» будет иметь стоимость 1+3 или 4.

Узел 3 является соседом узла 2. Однако на предыдущем шаге мы рассчитали его стоимость, которая составила 7. Теперь, если наш путь 1-2-3, узел 3 будет иметь стоимость 10. Путь 1-2- 3 будут стоить 10, а от 1 до 3 — 7.

Шаг 4) Для узла 3: соседний узел равен 7. Итак, сравнивая текущее значение узла 7 со стоимостью пути (7+1) или 8, мы обновим стоимость узла 7. То есть 8.

Итак, мы находим путь от узла 1 до узла 7, и это 1→ 3→ 7. Стоимость равна 8.

Шаг 5) Для узла 4: мы соответствующим образом обновим стоимость соседнего узла. Итак, узел «5» будет иметь обновленную стоимость 8. После шага 4,5 это будет выглядеть так:

Теперь путь 1-3-7 имеет стоимость 8 (ранее). Узел «7» не был помечен как посещенный, поскольку мы можем добраться до узла «7» из узла «6». Путь «1-2-6» имел стоимость 4. Значит, путь 1-2-6-7 будет иметь стоимость 7.

Поскольку 7 < 8, поэтому кратчайший путь от исходной вершины «1» до целевой вершины «7» будет 1-2-6-7, а стоимость равна 7. Раньше это было 1-3-7, а стоимость было 8.

Итак, окончательный график будет выглядеть так:

Ребро, отмеченное черной линией, — это наш кратчайший путь от 1 до 7, и он будет стоить нам 7.

Псевдокод Алгоритм Дейкстры

Вот псевдокод алгоритма Дейкстры.

Dijkstra(G, S):  
  for each vertex V in G
    distance[V] & lt; - Infinity
    previous[V] & lt; - NULL
  if V does not equal S, then, 
    (priority queue) Q.push(V)
  distance[S] = 0
  While Q is not empty
   U & lt; - Extract the MIN from Q
   For each unvisited adjacent V of U
   TotalDistance & lt; - distance[U] + edge_cost(U, V)
   if TotalDistance is less than distance[V], then
     distance[V] & lt; - TotalDistance
     previous[V] & lt; - u
  return distance, previous

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

Чтобы реализовать алгоритм Дейкстры, используя C++, вот код:

#include <bits/stdc++.h>
using namespace std;
#define size 7
int minimumDistance(int distance[], bool visited[]) {
  int min = INT_MAX;
  int min_index = INT_MAX;
  for (int i = 0; i < size; i++) {
    if (!visited[i] & amp; & distance[i] <= min) {
      min = distance[i];
      min_index = i;
    }
  }
  return min_index;
}
void printParentPath(int parent[], int i) {
  if (parent[i] == -1) {
    return;
  }
  printParentPath(parent, parent[i]);
  cout << i + 1 << " ";
}
void dijkstra(int graph[size][size], int source) {
  int distance[size];
  bool visited[size];
  int parent[size];
  for (int i = 0; i < size; i++) {
    parent[0] = -1;
    distance[i] = INT_MAX;
    visited[i] = false;
  }
  distance[source] = 0;
  for (int i = 0; i < size - 1; i++) {
    int U = minimumDistance(distance, visited);
    visited[U] = true;
    for (int j = 0; j < size; j++) {
      int curr_distance = distance[U] + graph[U][j];
      if (!visited[j] & amp; & graph[U][j] & amp; &
          curr_distance < distance[j]) {
        parent[j] = U;
        distance[j] = curr_distance;
      }
    }
  }
  cout << "Vertex\t\tDistance\tPath" << endl;
  for (int i = 1; i < size; i++) {
    cout << source + 1 << "->" << i + 1 << "\t\t" << distance[i] << "\t\t"
         << source + 1 << " ";
    printParentPath(parent, i);
    cout << endl;
  }
}
int main() {
  int graph[size][size] = {{0, 1, 7, 6, 0, 0, 0}, {1, 0, 9, 0, 0, 3, 0},
                           {7, 9, 0, 0, 0, 0, 1}, {6, 0, 0, 0, 2, 0, 0},
                           {0, 0, 0, 2, 0, 0, 0}, {0, 3, 0, 0, 0, 0, 3},
                           {0, 0, 0, 0, 5, 3, 0}};
  dijkstra(graph, 0);
}

Вывод:

Vertex     Distance        Path

1->2           1             1 2
1->3           7             1 3
1->4           6             1 4
1->5           8             1 4 5
1->6           4             1 2 6
1->7           7             1 2 6 7

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

Чтобы реализовать алгоритм Дейкстры, используя питон, вот код:

num_of_vertex = 7
def minimumDistance(distance, visited): 
  _min = 1e11
  min_index = 1e11
for i in range(num_of_vertex): 
  if not visited[i] and distance[i] & lt; = _min: 
   _min = distance[i]
   min_index = i
return min_index
def printParentNode(parent, i): 
  if parent[i] == -1: 
   return
  printParentNode(parent, parent[i])
  print("{} ".format(i + 1), end = "")
def dijkstra(graph, src): 
  distance = list()
  visited = list()
  parent = list()
for i in range(num_of_vertex): 
  parent.append(-1)
  distance.append(1e11)
  visited.append(False)
distance[src] = 0
for i in range(num_of_vertex - 1): 
  U = minimumDistance(distance, visited)
  visited[U] = True
for j in range(num_of_vertex): 
  curr_distance = distance[U] + graph[U][j]
  if not visited[j] and graph[U][j] and curr_distance & lt;
    distance[j]: parent[j] = U
    distance[j] = curr_distance
  print("Vertex\t\tDistance\tPath")
for i in range(num_of_vertex): 
  print("{}->{}\t\t{}\t\t{} 
".format(src + 1, i + 1, distance[i], src + 1), end = "")
  printParentNode(parent, i)
print("")
graph = [
  [0, 1, 7, 6, 0, 0, 0],
  [1, 0, 9, 0, 0, 3, 0],
  [7, 9, 0, 0, 0, 0, 1],
  [6, 0, 0, 0, 2, 0, 0],
  [0, 0, 0, 2, 0, 0, 0],
  [0, 3, 0, 0, 0, 0, 3],
  [0, 0, 0, 0, 5, 3, 0]
]
dijkstra(graph, 0)

Вывод:

Vertex     Distance        Path

1->1           0              1
1->2           1              1 2
1->3           7              1 3
1->4           6              1 4
1->5           8              1 4 5
1->6           4              1 2 6
1->7           7              1 2 6 7

Мы видим, что алгоритм вычисляет кратчайшее расстояние от исходного узла.

Применение алгоритма Дейкстры

Алгоритм Дейкстры имеет большой набор применений. Среди них он широко используется в области сетевых технологий. Вот некоторые примеры реального использования алгоритма Дейкстры:

Дейкстра на карте Google: По сути, этот алгоритм является основой для поиска кратчайших путей. Как мы видим из приведенного выше фрагмента кода.

Google не использует простой алгоритм Дейкстры. Вместо этого он использует модифицированную версию. Когда вы выбираете пункт назначения, он показывает несколько путей на карте Google. Среди этих путей для пользователя отбираются некоторые пути. Эти выбранные пути основаны на «времени». Итак, «время» — это граничная стоимость кратчайшего пути.

Дейкстра в IP-маршрутизации: IP маршрутизации это сетевая терминология. Это означает, как ваш пакет данных отправляется получателю по разным путям. Эти пути состоят из маршрутизаторов, серверов и т. д. В IP-маршрутизации существуют разные типы протоколов.

Эти протоколы помогают маршрутизатору найти кратчайшие пути для отправки данных. Одно из названий протокола — «OSPF (сначала открывайте кратчайший путь)». OSPF использует алгоритм Дейкстры. Маршрутизатор поддерживает таблицу маршрутов. Каждый маршрутизатор использует свою таблицу совместно с соседними маршрутизаторами. Получив обновленную таблицу, они должны заново рассчитать все пути. В это время маршрутизатор использует алгоритм Дейкстры.

Ограничение алгоритма Дейкстры

Алгоритм Дейкстры не может гарантировать кратчайший путь в графе с отрицательными ребрами. Алгоритм Дейкстры следует этим методологиям:

От одного узла к другому будет проложен один кратчайший путь.
После выбора кратчайшего пути между двумя узлами он не будет рассчитываться повторно.

Здесь обратите внимание на два примера с отрицательными краями.

На левом графике есть три вершины. Дейкстра будет работать на Graph следующим образом:

Шаг 1) Начальная вершина «1» будет инициализирована нулем. Остальные узлы будут иметь бесконечность.

Шаг 2) Отметьте узел «1» как посещенный и включите его в кратчайший путь.

Шаг 3) Расстояние от исходного узла 1 до узлов «2» и «3» установлено равным бесконечности, поскольку кратчайший путь еще не рассчитан. Таким образом, любой путь, стоимость которого меньше бесконечности, будет добавлен к кратчайшему пути (жадный подход).

Шаг 4) Обновление расстояния от исходной вершины или исходного узла «1» до «2». Текущий вес будет 5 (5

Шаг 5) Теперь, если мы проверим кратчайшие расстояния от узла «1», мы обнаружим, что 5 — это кратчайшее расстояние для ребра 1–> 2. Таким образом, узел «2» будет помечен как посещенный.

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

Однако, если мы посмотрим, существует путь 1-3-2, который будет стоить всего 2 доллара. Но Дейкстра показывает, что от узла «1» до узла «2» кратчайшее расстояние равно 5. Итак, Дейкстра не смог вычислить кратчайшее расстояние. расстояние правильно. Причина, по которой это произошло, заключается в том, что Дейкстра — жадный алгоритм. Таким образом, как только узел будет помечен как посещенный, он не будет повторно рассматриваться, хотя может быть доступен более короткий путь. Эта проблема возникает только в том случае, если ребра имеют отрицательную стоимость или отрицательный вес ребер.

Дейкстра не может вычислить кратчайший путь между двумя узлами в этом сценарии. В результате этот алгоритм имеет некоторые недостатки. Для решения этой проблемы с отрицательным краем используется другой алгоритм, называемый «алгоритм Беллмана-Форда». Этот алгоритм может работать с отрицательными фронтами.

Сложность алгоритма Дейкстры

В приведенной выше реализации использовались два цикла «for». Эти циклы выполняются для количества вершин. Итак, временная сложность О(В²). Здесь термин «0» означает обозначение, которое дает предположение для алгоритма Дейкстры.

Мы можем сохранить график, используя «Приоритетную очередь». Очередь приоритетов представляет собой структуру данных двоичной кучи. Это будет более эффективно, чем 2D-матрица. Преимущество, которое будет иметь минимальную стоимость, будет иметь высокий приоритет.

Тогда временная сложность будет O (E журнал (V)). Здесь E — количество ребер, а V — количество вершин.

Космическая сложность О(В²), поскольку мы используем матрицу смежности (2D массив). Сложность пространства можно оптимизировать с помощью списка смежности или структуры данных очереди.

Вы могли бы: