Ο Αλγόριθμος του Dijkstra στο Python & C++ (Παράδειγμα)

Ποια είναι η Συντομότερη Διαδρομή ή η Συντομότερη Απόσταση;

Μια διαδρομή από την κορυφή πηγής προς την κορυφή προορισμού που κοστίζει ένα ελάχιστο ποσό είναι η συντομότερη διαδρομή ή η συντομότερη απόσταση. Στη θεωρία γραφημάτων, είναι δυνατό να υπάρχουν πολλαπλές διαδρομές από μια πηγή σε έναν προορισμό. Μεταξύ αυτών των διαδρομών, εάν υπάρχει μια διαδρομή που κοστίζει ένα ελάχιστο ποσό, την ονομάζουμε συντομότερη διαδρομή.

Εδώ, ο όρος «κόστος» αναφέρεται στον αριθμό των κόμβων στη διαδρομή ή στο άθροισμα του κόστους σε κάθε ακμή. Μια διαδρομή μπορεί να έχει μία ή πολλαπλές ακμές. Η σύνδεση μεταξύ δύο κορυφών ονομάζεται «ακμή». Υπάρχουν διάφοροι τύποι αλγορίθμων συντομότερης διαδρομής, όπως ο Αλγόριθμος Dijkstra και ο Αλγόριθμος Bellman-Ford.

Εδώ, συζητάμε τον Αλγόριθμο του Dijkstra. Ας δούμε το ακόλουθο σταθμισμένο γράφημα:

Ένα μη κατευθυνόμενο-σταθμισμένο γράφημα

• Ο όρος «σταθμισμένο» σημαίνει το κόστος μετάβασης από έναν κόμβο σε έναν άλλο. Για παράδειγμα, κατά τη μετάβαση από τον κόμβο 1 στον κόμβο 2, το κόστος ή το βάρος είναι 1.
• Η διαδρομή μεταξύ του κόμβου 1 και του κόμβου 2 ονομάζεται άκρη.
• «Μη κατευθυνόμενο» σημαίνει ότι μπορείτε να μετακινηθείτε από έναν κόμβο σε έναν άλλο και πίσω στον προηγούμενο κόμβο. Έτσι, αν προσπαθήσουμε να βρούμε όλες τις διαδρομές από τον κόμβο 1 στον κόμβο 7, αυτές θα είναι:

Μεταξύ αυτών των τεσσάρων διαδρομών, μπορούμε να δούμε ότι η πρώτη διαδρομή κοστίζει 7. Επομένως, είναι η συντομότερη διαδρομή από άποψη κόστους.

Συντομότερη διαδρομή

Πώς λειτουργεί ο αλγόριθμος του Dijkstra

Ο αλγόριθμος του Dijkstra μπορεί να βρει τη μικρότερη απόσταση τόσο σε κατευθυνόμενα όσο και σε μη κατευθυνόμενα σταθμισμένα γραφήματα. Αυτός ο αλγόριθμος είναι άπληστος επειδή επιλέγει πάντα τον μικρότερο ή πλησιέστερο κόμβο από την αρχή. Ο όρος «άπληστος» σημαίνει ότι μεταξύ ενός συνόλου αποτελεσμάτων ή αποτελεσμάτων, ο αλγόριθμος θα επιλέξει το καλύτερο από αυτά.

Εδώ, προσπαθούμε να βρούμε τις συντομότερες διαδρομές μεταξύ όλων των άλλων διαδρομών. Έτσι, ο Αλγόριθμος του Dijkstra βρίσκει όλες τις συντομότερες διαδρομές από έναν μόνο κόμβο πηγής. Ως αποτέλεσμα, συμπεριφέρεται σαν άπληστος αλγόριθμος.

Στην παρακάτω ενότητα «παράδειγμα», θα δείτε την βήμα προς βήμα προσέγγιση. Λειτουργεί ως εξής:

Βήμα 1) Αρχικοποιήστε τον αρχικό κόμβο με 0 κόστος και τους υπόλοιπους κόμβους με άπειρο κόστος.
Βήμα 2) Διατήρηση ενός πίνακα ή λίστας για διατήρηση track των επισκεπτόμενων κόμβων.
Βήμα 3) Ενημερώστε το κόστος κόμβου με το ελάχιστο κόστος. Αυτό μπορεί να γίνει συγκρίνοντας το τρέχον κόστος με το κόστος διαδρομής (που παρουσιάζεται στην ενότητα παραδειγμάτων).
Βήμα 4) Συνεχίστε το βήμα 3 μέχρι να επισκεφθούν όλοι οι κόμβοι.

Αφού ολοκληρώσουμε όλα αυτά τα βήματα, θα βρούμε τη διαδρομή που κοστίζει ελάχιστο από την πηγή στον προορισμό.

Διαφορά μεταξύ Dijkstra και BFS, DFS

Η κύρια διαφορά μεταξύ του Dijkstra και του BFS-DFS είναι ότι ο Dijkstra είναι ένας αλγόριθμος εύρεσης της συντομότερης διαδρομής, ενώ ο BFS και ο DFS είναι γενικοί αλγόριθμοι εύρεσης διαδρομής. Σε γενικές περιπτώσεις, ο BFS και ο DFS δεν λαμβάνουν υπόψη το κόστος ακμής κατά την εύρεση της διαδρομής. Επομένως, αυτοί οι αλγόριθμοι δεν μπορούν να εγγυηθούν τη συντομότερη διαδρομή.

Επίδειξη 2D πλέγματος για το πώς λειτουργεί το BFS

Αλγοσκίτσο, που δείχνει επίδειξη 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 μπορεί να βρει μια διαδρομή από την πηγή (κορυφή εκκίνησης) στον προορισμό.
• Δεν μπορεί να εγγυηθεί εάν η διαδρομή που ανακαλύφθηκε από τον κόμβο πηγής στον προορισμό είναι η συντομότερη διαδρομή ή όχι.

Ωστόσο, όσον αφορά τον αλγόριθμο του Dijkstra, επιλέγει ακμές με βάση το κόστος τους. Ως άπληστος αλγόριθμος, θα επιλέξει τις διαδρομές με το ελάχιστο κόστος.

Παράδειγμα αλγόριθμου Dijkstra

Ο αλγόριθμος του Dijkstra χρησιμοποιεί το κόστος ή το βάρος για να υπολογίσει το συνολικό κόστος της διαδρομής.

Ο στόχος του αλγόριθμου της Dijkstra είναι να ελαχιστοποιήσει αυτό το συνολικό κόστος ή βάρος. Στο παράδειγμα που φαίνεται παραπάνω, βρίσκουμε τις καλύτερες διαδρομές από τον κόμβο 1 στον κόμβο 7 και, στη συνέχεια, υπολογίζουμε όλα τα κόστη.

Στον Αλγόριθμο του Dijkstra, θα βρει τις συντομότερες διαδρομές υπολογίζοντας βάρη. Δεν θα αναζητήσει όλες τις πιθανές διαδρομές. Ας δείξουμε τον Αλγόριθμο του Dijkstra με ένα παράδειγμα. Για παράδειγμα, σας έχει ζητηθεί να βρείτε τη συντομότερη διαδρομή από τον κόμβο 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

Εδώ είναι ο ψευδοκώδικας για τον αλγόριθμο του Dijkstra:

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++ Υλοποίηση του Αλγορίθμου του Dijkstra

Για να εφαρμόσετε τον αλγόριθμο του Dijkstra χρησιμοποιώντας 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 Υλοποίηση του Αλγορίθμου του Dijkstra

Για να εφαρμόσετε τον αλγόριθμο του Dijkstra χρησιμοποιώντας 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

Μπορούμε να δούμε ότι ο αλγόριθμος υπολογίζει τη μικρότερη απόσταση από τον κόμβο πηγής.

Εφαρμογή του αλγορίθμου Dijkstra

Ο αλγόριθμος του Dijkstra έχει ένα ευρύ φάσμα χρήσεων. Μεταξύ αυτών, χρησιμοποιείται ευρέως στον τομέα των δικτύων. Ακολουθούν ορισμένες χρήσεις του αλγορίθμου του Dijkstra στην πραγματική ζωή:

Ντάικστρα στο Google Χάρτες: Αυτός ο αλγόριθμος αποτελεί τη ραχοκοκαλιά για την εύρεση των συντομότερων διαδρομών, όπως μπορούμε να δούμε από το παραπάνω αποτέλεσμα του αποσπάσματος κώδικα.

Google δεν χρησιμοποιεί τον απλό αλγόριθμο Dijkstra. Αντίθετα, χρησιμοποιεί μια τροποποιημένη έκδοση. Όταν επιλέγετε έναν προορισμό, σας δείχνει πολλαπλές διαδρομές σε Google Χάρτες. Μεταξύ αυτών των διαδρομών, μερικές έχουν ταξινομηθεί για τον χρήστη. Αυτές οι διαδρομές επιλέγονται με βάση τον «χρόνο». Έτσι, ο «χρόνος» είναι ένα κόστος πλεονάσματος για τη συντομότερη διαδρομή.

Dijkstra στη δρομολόγηση IP: Δρομολόγηση IP είναι μια ορολογία δικτύωσης. Περιγράφει τον τρόπο με τον οποίο το πακέτο δεδομένων σας αποστέλλεται στον παραλήπτη μέσω διαφορετικών διαδρομών. Αυτές οι διαδρομές αποτελούνται από δρομολογητές, διακομιστές και άλλο εξοπλισμό. Στη δρομολόγηση IP, υπάρχουν διαφορετικοί τύποι πρωτοκόλλων.

Αυτά τα πρωτόκολλα βοηθούν τον δρομολογητή να βρει τις συντομότερες διαδρομές για την αποστολή των δεδομένων. Ένα από τα ονόματα πρωτοκόλλου είναι "OSPF (Open Shortest Path First)". Το OSPF χρησιμοποιεί τον αλγόριθμο του Dijkstra. Ο δρομολογητής διατηρεί έναν πίνακα διαδρομών. Κάθε δρομολογητής μοιράζεται τον πίνακά του με γειτονικούς δρομολογητές. Αφού λάβει τον ενημερωμένο πίνακα, πρέπει να υπολογίσουν ξανά όλες τις διαδρομές. Εκείνη τη στιγμή, ο δρομολογητής χρησιμοποιεί τον αλγόριθμο του Dijkstra.

Περιορισμός του αλγορίθμου του Dijkstra

Ο αλγόριθμος του Dijkstra δεν μπορεί να εγγυηθεί τη συντομότερη διαδρομή σε ένα γράφημα με αρνητικές ακμές. Ο αλγόριθμος του Dijkstra ακολουθεί τις ακόλουθες αρχές:

• Ένα συντομότερο μονοπάτι θα ληφθεί από τον έναν κόμβο στον άλλο.
• Μόλις επιλεγεί η συντομότερη διαδρομή μεταξύ δύο κόμβων, δεν θα υπολογιστεί ξανά.

Εδώ, παρατηρήστε δύο παραδείγματα με αρνητικές ακμές.

Στο αριστερό γράφημα, υπάρχουν τρεις κορυφές. Το Dijkstra θα εκτελεστεί στο γράφημα ως εξής:

Βήμα 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. Αλλά ο Dijkstra δείχνει ότι από τον κόμβο "1" στον κόμβο "2", η συντομότερη απόσταση είναι 5. Έτσι, ο Dijkstra απέτυχε να υπολογίσει σωστά τη συντομότερη απόσταση. Ο λόγος είναι ότι ο Dijkstra είναι ένας άπληστος αλγόριθμος. Έτσι, μόλις ένας κόμβος επισημανθεί ως επισκεπτόμενος, δεν θα επανεξεταστεί, αν και μπορεί να υπάρχει μια μικρότερη διαδρομή διαθέσιμη. Αυτό το πρόβλημα παρουσιάζεται μόνο όταν οι ακμές έχουν αρνητικό κόστος ή αρνητικό βάρος στις ακμές.

Ο Dijkstra αποτυγχάνει να υπολογίσει τη συντομότερη διαδρομή μεταξύ δύο κόμβων σε αυτό το σενάριο. Ως αποτέλεσμα, αυτός ο αλγόριθμος έχει ορισμένα μειονεκτήματα. Για την επίλυση αυτού του προβλήματος αρνητικών ακμών, χρησιμοποιείται ένας άλλος αλγόριθμος που ονομάζεται «Αλγόριθμος Bellman-Ford». Αυτός ο αλγόριθμος μπορεί να λειτουργήσει με αρνητικές ακμές.

Πολυπλοκότητα αλγορίθμου Dijkstra

Η παραπάνω υλοποίηση χρησιμοποίησε δύο βρόχους «για». Αυτοί οι βρόχοι τρέχουν για τον αριθμό των κορυφών. Άρα, η χρονική πολυπλοκότητα είναι O(V²)Εδώ, ο όρος «O» είναι μια σημειογραφία που δίνει μια υπόθεση για τον αλγόριθμο Dijkstra.

Μπορούμε να αποθηκεύσουμε το γράφημα χρησιμοποιώντας μια «ουρά προτεραιότητας». Μια ουρά προτεραιότητας είναι μια δομή δεδομένων δυαδικού σωρού. Θα είναι πιο αποτελεσματική από έναν δισδιάστατο πίνακα. Μια ακμή με ελάχιστο κόστος θα έχει υψηλή προτεραιότητα. Τότε η χρονική πολυπλοκότητα θα είναι O(E log V). Εδώ, E είναι ο αριθμός των ακμών και V είναι ο αριθμός των κορυφών.

Η πολυπλοκότητα του χώρου είναι O(V²), καθώς χρησιμοποιούμε έναν πίνακα γειτνίασης (Τρισδιάστατος πίνακας). Η πολυπλοκότητα του χώρου μπορεί να βελτιστοποιηθεί χρησιμοποιώντας μια λίστα γειτνίασης ή μια δομή δεδομένων ουράς.

Συχνές Ερωτήσεις