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

Кой е най-краткият път или най-късото разстояние?

Път от изходния връх до крайния връх, който струва минимална сума, е най-краткият път или най-късото разстояние. В теорията на графите е възможно да има множество маршрути от източник до крайния връх. Сред тези маршрути, ако има маршрут, който струва минимална сума, го наричаме най-краткият път.

Тук „цена“ означава броя на възлите в маршрута или сумирането на разходите на всеки ръб. Пътят може да има един или множество ръбове. Връзката между два върха се нарича „ръб“. Съществуват различни видове алгоритми за най-краткия път, като например алгоритъма на Дейкстра и алгоритъма на Белман-Форд.

Тук ще обсъдим алгоритъма на Дейкстра. Нека разгледаме следната претеглена графика:

Неориентирана-претеглена графика

• Терминът „претеглено“ означава цената на преместването от един възел към друг. Например, при преместване от възел 1 към възел 2, цената или теглото е 1.
• Пътят между възел 1 и възел 2 се нарича ръб.
• „Неориентиран“ означава, че можете да се движите от един възел към друг и обратно към предишния възел. Така че, ако се опитаме да намерим всички маршрути от възел 1 до възел 7, те ще бъдат:

Сред тези четири маршрута виждаме, че първият маршрут струва 7. Така че, това е най-краткият път по отношение на разходите.

Най-краткият път

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

Алгоритъмът на Дейкстра може да намери най-късото разстояние както в насочени, така и в ненасочени претеглени графи. Този алгоритъм е алчен, защото винаги избира най-късия или най-близкия възел от началото на координатната система. Терминът „алчен“ означава, че измежду набор от резултати или резултати алгоритъмът ще избере най-добрия от тях.

Тук се опитваме да намерим най-късите пътища сред всички останали маршрути. Така че, алгоритъмът на Дейкстра намира всички най-къси пътища от един възел източник. В резултат на това той се държи като алчен алгоритъм.

В раздела „пример“ по-долу ще видите стъпка по стъпка подхода. Той работи по следния начин:

Стъпка 1) Инициализирайте началния възел с 0 цена, а останалите възли с безкрайна цена.
Стъпка 2) Поддържайте масив или списък, който да съхранявате track от посетените възли.
Стъпка 3) Актуализирайте цената на възела с минималната цена. Това може да се направи чрез сравняване на текущата цена с цената на пътя (показано в примерния раздел).
Стъпка 4) Продължете стъпка 3, докато не бъдат посетени всички възли.

След като изпълним всички тези стъпки, ще намерим пътя, който струва минимум от източника до дестинацията.

Разлика между Dijkstra и BFS, DFS

Основната разлика между алгоритъма на Дейкстра и BFS-DFS е, че Дейкстра е алгоритъм за намиране на най-кратък път, докато BFS и DFS са общи алгоритми за намиране на път. В общи случаи BFS и DFS не отчитат цената на ръба при намиране на пътя. Следователно, тези алгоритми не могат да гарантират най-краткия път.

2D мрежова демонстрация на това как работи BFS

Algosketch, показващ BFS демонстрация

Тази демонстрация показва, че BFS намира само пътя. Въпреки това не се интересува от теглото на пътя. BFS (Търсене в ширина) предполага, че пътуването от един възел до друг възел ще струва само 1.

Нека видим примерна графика:

Тук BFS намира път на ниво 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.

Прякор 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 маршрутизацията има различни видове протоколи.

Тези протоколи помагат на рутера да намери най-кратките пътища за изпращане на данните. Едно от имената на протоколите е „OSPF (Open Shortest Path First)“. OSPF използва алгоритъма на Дейкстра. Рутерът поддържа таблица с маршрути. Всеки рутер споделя своята таблица със съседните рутери. След получаване на актуализираната таблица, те трябва да изчислят всички пътища отново. В този момент рутерът използва алгоритъма на Дейкстра.

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

Алгоритъмът на Дейкстра не може да гарантира най-краткия път в граф с отрицателни ръбове. Алгоритъмът на Дейкстра следва следните принципи:

• Един най-кратък път ще бъде изведен от един възел до друг.
• След като бъде избран най-краткият път между два възела, той няма да бъде изчислен отново.

Тук забележете два примера с отрицателни ръбове.

В лявата графика, има три върха. Дейкстра ще се изпълни върху графа по следния начин:

Стъпка 1) Началният връх “1” ще бъде инициализиран на нула. Останалите възли ще имат безкрайност.

Стъпка 2) Маркирайте възел „1“ като посетен и го включете в най-краткия път.

Стъпка 3) Разстоянието от изходния възел 1 до възлите „2“ и „3“ е зададено на безкрайност, тъй като най-късият път все още не е изчислен. Така че всеки път, който струва по-малко от безкрайност, ще бъде добавен към най-късия път (алчен подход).

Стъпка 4) Актуализиране на разстоянието от изходния връх „1“ на „2“. Текущото тегло ще бъде 5 (5 < безкрайност). По подобен начин актуализирайте разстоянието от възел „1“ на „3“ с тегло 3.

Стъпка 5) Сега, ако проверим най-късите разстояния от възел „1“, ще открием, че 5 е най-късото разстояние за ръб 1→2. Така че, възел „2“ ще бъде маркиран като посетен. По подобен начин, възел „3“ също ще бъде маркиран като посетен, тъй като най-късото разстояние е 3.

Ако обаче наблюдаваме, има път 1-3-2, който ще струва само 2. Но Дейкстра показва, че от възел „1“ до възел „2“ най-късото разстояние е 5. Така че, Дейкстра не е успял да изчисли правилно най-късото разстояние. Причината е, че Дейкстра е алгоритъм с алгоритъм „грейд“. Така че, след като даден възел бъде маркиран като посетен, той няма да бъде преразгледан, въпреки че може да има наличен по-кратък път. Този проблем възниква само когато ръбовете имат отрицателни разходи или ръбове с отрицателно тегло.

В този сценарий Дейкстра не успява да изчисли най-краткия път между два възела. В резултат на това този алгоритъм има някои недостатъци. За да се реши този проблем с отрицателните ръбове, се използва друг алгоритъм, наречен „алгоритъм на Белман-Форд“. Този алгоритъм може да работи с отрицателни ръбове.

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

Реализацията по-горе използва два цикъла „за“. Тези цикли се изпълняват за броя на върховете. И така, времевата сложност е O(V²)Тук терминът „O“ е обозначение, което дава предположение за алгоритъма на Дейкстра.

Можем да съхраним графиката, използвайки „опашка с приоритет“. Опашката с приоритет е двоична структура от данни тип „heap“. Тя ще бъде по-ефективна от 2D матрица. Ребро с минимална цена ще има висок приоритет. Тогава времевата сложност ще бъде O(E log V). Тук E е броят на ръбовете, а V е броят на върховете.

Космическата сложност е O(V²), тъй като използваме матрица на съседство (2D масив). Сложността на пространството може да бъде оптимизирана с помощта на списък със съседство или структура от данни на опашка.

Въпроси и Отговори