Алгоритм Дейкстры в Python & C++ (Пример)

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

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

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

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

Неориентированный взвешенный граф

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

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

Кратчайший путь

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

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

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

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

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

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

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

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

Демонстрация работы алгоритма BFS на основе 2D-сетки

Алгоскетч, показывает демонстрацию BFS

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

Рассмотрим пример графика:

Здесь алгоритм BFS находит путь на втором уровне. 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.

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

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

Dijkstra(G, S):
  for each vertex V in G
    distance[V] <- Infinity
    previous[V] <- NULL
    if V does not equal S, then,
      (priority queue) Q.push(V)
  distance[S] = 0
  While Q is not empty
    U <- Extract the MIN from Q
    For each unvisited adjacent V of U
      TotalDistance <- distance[U] + edge_cost(U, V)
      if TotalDistance is less than distance[V], then
        distance[V] <- TotalDistance
        previous[V] <- 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] && 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] && graph[U][j] &&
          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 Реализация алгоритма Дейкстры

Чтобы реализовать алгоритм Дейкстры, используя 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] <= _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 < 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-маршрутизация — это сетевой термин. Он описывает, как ваш пакет данных отправляется получателю по различным путям. Эти пути включают маршрутизаторы, серверы и другое оборудование. В IP-маршрутизации существуют различные типы протоколов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Мы можем хранить граф, используя «очередь с приоритетами». Очередь с приоритетами — это структура данных типа «бинарная куча». Она будет эффективнее, чем двумерная матрица. Ребро с минимальной стоимостью будет иметь высокий приоритет. Тогда временная сложность составит O(E log V). Здесь E — количество ребер, а V — количество вершин.

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

Часто задаваемые вопросы (FAQ)