Αλγόριθμος Dijsktra: C++, Python Παράδειγμα κώδικα
Σάρα Τσεν
Ποιο είναι το συντομότερο μονοπάτι ή η μικρότερη απόσταση;
Μια διαδρομή από την κορυφή της πηγής στην κορυφή προορισμού που κοστίζει ελάχιστο είναι η συντομότερη διαδρομή ή η μικρότερη απόσταση. Στη θεωρία γραφημάτων, είναι δυνατό να υπάρχουν πολλαπλές διαδρομές από μια πηγή σε έναν προορισμό. Μεταξύ αυτών των διαδρομών, εάν υπάρχει μια διαδρομή που κοστίζει ένα ελάχιστο ποσό, μπορούμε να την ονομάσουμε αλγόριθμο της συντομότερης διαδρομής.
Εδώ "Κόστος" σημαίνει τον αριθμό των κόμβων στη διαδρομή ή το άθροισμα του κόστους σε κάθε διαδρομή. Μια διαδρομή μπορεί να έχει μία ή πολλές ακμές. Η σύνδεση μεταξύ δύο κορυφών ονομάζεται "άκρη". Υπάρχουν διάφοροι τύποι αλγορίθμων συντομότερης διαδρομής, όπως ο αλγόριθμος του Dijkstra, ο αλγόριθμος Bellman-Ford κ.λπ.
Εδώ, συζητάμε για τον Αλγόριθμο του Dijkstra
Ας δούμε το παρακάτω σταθμισμένο γράφημα:
- Ο όρος «Σταθμισμένο» σημαίνει μετακίνηση κόστους από τον έναν κόμβο στον άλλο. Για παράδειγμα, μεταβαίνοντας από τον κόμβο 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. Άρα, είναι η συντομότερη διαδρομή από άποψη κόστους.
Πώς λειτουργεί ο αλγόριθμος του Dijkstra
Ο αλγόριθμος Dijkstra μπορεί να βρει τη μικρότερη απόσταση τόσο σε κατευθυνόμενα όσο και σε μη κατευθυνόμενα σταθμισμένα γραφήματα. Αυτός ο Αλγόριθμος είναι άπληστος επειδή επιλέγει πάντα τον συντομότερο ή τον πλησιέστερο κόμβο από την αρχή. Ο όρος "άπληστος" σημαίνει ότι μεταξύ ενός συνόλου αποτελεσμάτων ή αποτελεσμάτων, ο Αλγόριθμος θα επιλέξει το καλύτερο από αυτά.
Εδώ, προσπαθούμε να βρούμε τα συντομότερα μονοπάτια μεταξύ όλων των άλλων διαδρομών. Έτσι, ο αλγόριθμος του Dijkstra βρίσκει όλα τα συντομότερα μονοπάτια από έναν μόνο κόμβο προορισμού. Ως αποτέλεσμα, συμπεριφέρεται σαν α άπληστος αλγόριθμος.
Στην ενότητα "παράδειγμα" παρακάτω, θα δείτε την προσέγγιση βήμα προς βήμα. Λειτουργεί ως εξής:
Βήμα 1) Αρχικοποιήστε τον αρχικό κόμβο με 0 κόστη και τον υπόλοιπο κόμβο ως Κόστος απεριόριστου.
Βήμα 2) Διατηρήστε έναν πίνακα ή λίστα για να παρακολουθείτε τους κόμβους που επισκέπτεστε
Βήμα 3) Ενημερώστε το κόστος κόμβου με το ελάχιστο κόστος. Μπορεί να γίνει συγκρίνοντας το τρέχον κόστος με το κόστος διαδρομής. (Η επίδειξη φαίνεται στην ενότητα του παραδείγματος)
Βήμα 4) Συνεχίστε το βήμα 3 μέχρι να επισκεφθείτε όλο τον κόμβο.
Αφού ολοκληρώσουμε όλα αυτά τα βήματα, θα βρούμε τη διαδρομή που κοστίζει ελάχιστο από την πηγή στον προορισμό.
Διαφορά μεταξύ Dijkstra και BFS, DFS
Η κύρια διαφορά μεταξύ Dijkstra και BFS-DFS είναι ότι ο Dijkstra είναι ο συντομότερος αλγόριθμος εύρεσης μονοπατιών και ο BFS, DFS είναι ο αλγόριθμος εύρεσης μονοπατιών. Σε γενικές περιπτώσεις, το BFS και το DFS δεν λαμβάνουν υπόψη το κόστος κατά την εύρεση της διαδρομής. Έτσι, αυτοί οι αλγόριθμοι δεν μπορούν να εγγυηθούν τη συντομότερη διαδρομή.
Δισδιάστατη επίδειξη πλέγματος του τρόπου λειτουργίας του BFS
Αυτή η επίδειξη υποδεικνύει ότι το 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 μπορεί να βρει μια διαδρομή από την πηγή (κορυφή εκκίνησης) στον προορισμό.
- Δεν μπορεί να εγγυηθεί εάν η διαδρομή που ανακαλύφθηκε από τον κόμβο πηγής στον προορισμό είναι η συντομότερη διαδρομή ή όχι.
Ωστόσο, όσον αφορά τον αλγόριθμο Dijkstra, θα επιλέξει άκρες με βάση το κόστος τους. Ως άπληστος αλγόριθμος, θα επιλέξει τις καλύτερες ή ελάχιστες διαδρομές κόστους.
Παράδειγμα αλγόριθμου Dijkstra
Ο αλγόριθμος του Dijkstra χρησιμοποιεί το κόστος ή το βάρος για να υπολογίσει το συνολικό κόστος της διαδρομής.
Ο στόχος του αλγόριθμου της Dijkstra είναι να ελαχιστοποιήσει αυτό το συνολικό κόστος ή βάρος. Στο παράδειγμα που φαίνεται παραπάνω, βρίσκουμε τις καλύτερες διαδρομές από τον κόμβο 1 στον κόμβο 7 και, στη συνέχεια, υπολογίζουμε όλα τα κόστη.
Στον αλγόριθμο του Dijkstra, θα βρει τα συντομότερα μονοπάτια υπολογίζοντας τα βάρη. Δεν θα αναζητήσει όλα τα πιθανά μονοπάτια. Ας δείξουμε τον Αλγόριθμο του Dijkstra με ένα παράδειγμα. Για παράδειγμα, σας ζητήθηκε να βρείτε τη συντομότερη διαδρομή από τον κόμβο 1 έως 7.
Για αυτή τη διαδικασία, τα βήματα δίνονται παρακάτω:
Βήμα 1) Αρχικοποιήστε το κόστος του αρχικού κόμβου στο 0.
Υπόλοιπο κόμβο, εκχώρηση "Inf". Σημαίνει ότι δεν υπάρχει μονοπάτι μεταξύ της αρχικής κορυφής (της πηγής) και του κόμβου ή η διαδρομή δεν έχει γίνει ακόμη επίσκεψη.
Βήμα 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
Εδώ είναι ο ψευδοκώδικας για τον αλγόριθμο του Dijkstra
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++ υλοποίηση Αλγόριθμος 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] & 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 υλοποίηση Αλγόριθμος Dijkstra
Για να εφαρμόσετε τον αλγόριθμο του Dijkstra χρησιμοποιώντας Πύθων, ορίστε ο κωδικός:
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
Μπορούμε να δούμε ότι ο Αλγόριθμος υπολογίζει τη μικρότερη απόσταση από τον κόμβο πηγής.
Εφαρμογή του αλγορίθμου Dijkstra
Το Dijkstra Algo έχει ένα μεγάλο σύνολο χρήσεων. Μεταξύ αυτών, χρησιμοποιείται ευρέως, στον τομέα της δικτύωσης. Ακολουθούν μερικές από τις πραγματικές χρήσεις του αλγόριθμου του Dijkstra:
Dijkstra στον χάρτη Google: Βασικά, αυτός ο Αλγόριθμος είναι η ραχοκοκαλιά για την εύρεση των συντομότερων μονοπατιών. Όπως μπορούμε να δούμε από την παραπάνω έξοδο αποσπάσματος κώδικα.
Η Google δεν χρησιμοποιεί τον απλό αλγόριθμο Dijkstra. Αντίθετα, χρησιμοποιεί μια τροποποιημένη έκδοση. Όταν επιλέγετε έναν προορισμό, σας εμφανίζει πολλαπλές διαδρομές στον Χάρτη Google. Μεταξύ αυτών των διαδρομών, ορισμένες διαδρομές ταξινομούνται για τον χρήστη. Αυτές οι διαδρομές που επιλέχθηκαν βασίζονται στον "χρόνο". Άρα, ο «χρόνος» είναι ένα πλεονέκτημα για τη συντομότερη διαδρομή.
Dijkstra στη δρομολόγηση IP: Δρομολόγηση IP είναι μια ορολογία δικτύωσης. Σημαίνει πώς το πακέτο δεδομένων σας αποστέλλεται στον παραλήπτη μέσω διαφορετικών διαδρομών. Αυτές οι διαδρομές αποτελούνται από δρομολογητές, διακομιστές κ.λπ. Στη δρομολόγηση IP, υπάρχουν διαφορετικοί τύποι πρωτοκόλλων.
Αυτά τα πρωτόκολλα βοηθούν τον δρομολογητή να βρει τις συντομότερες διαδρομές για την αποστολή των δεδομένων. Ένα από τα ονόματα πρωτοκόλλου είναι "OSPF (Πρώτα ανοιχτή η συντομότερη διαδρομή)". Το OSPF χρησιμοποιεί αλγόριθμο dijkstra. Ο δρομολογητής διατηρεί έναν πίνακα διαδρομών. Κάθε δρομολογητής μοιράζεται τον πίνακα του με γειτονικούς δρομολογητές. Αφού λάβουν τον ενημερωμένο πίνακα, πρέπει να υπολογίσουν ξανά όλες τις διαδρομές. Εκείνη τη στιγμή, ο δρομολογητής χρησιμοποιεί τον αλγόριθμο Dijkstra.
Περιορισμός του αλγορίθμου του Dijkstra
Ο αλγόριθμος Dijkstra δεν μπορεί να εγγυηθεί τη συντομότερη διαδρομή στο γράφημα της αρνητικής ακμής. Ο αλγόριθμος Dijkstra ακολουθεί αυτές τις μεθοδολογίες:
- Ένα συντομότερο μονοπάτι θα ληφθεί από τον έναν κόμβο στον άλλο.
- Μόλις επιλεγεί η συντομότερη διαδρομή μεταξύ δύο κόμβων, δεν θα υπολογιστεί ξανά.
Εδώ, παρατηρήστε δύο παραδείγματα με αρνητικές ακμές.
Στο αριστερό γράφημα, υπάρχουν τρεις κορυφές. Το Dijkstra θα τρέξει στο Graph ως εξής:
Βήμα 1) Η αρχική κορυφή "1" θα αρχικοποιηθεί στο μηδέν. Οι άλλοι κόμβοι θα έχουν άπειρο.
Βήμα 2) Επισημάνετε τον κόμβο "1" ως επισκέψιμο και συμπεριλάβετέ τον στη συντομότερη διαδρομή.
Βήμα 3) Η απόσταση του κόμβου πηγής 1 από τους κόμβους «2» και «3» έχει οριστεί στο άπειρο, καθώς η συντομότερη διαδρομή δεν έχει ακόμη υπολογιστεί. Έτσι, κάθε μονοπάτι που θα κοστίσει λιγότερο από το άπειρο θα προστεθεί στο συντομότερο μονοπάτι (greedy προσέγγιση).
Βήμα 4) Ενημέρωση της απόστασης από την κορυφή της πηγής ή τον κόμβο πηγής "1" στο "2". Το τρέχον βάρος θα είναι 5 (5
Βήμα 5) Τώρα, αν ελέγξουμε τις μικρότερες αποστάσεις από τον κόμβο «1», βρίσκουμε ότι το 5 είναι η μικρότερη απόσταση για την ακμή 1–> 2. Έτσι, ο κόμβος «2» θα επισημανθεί ως επισκέψιμος.
Ομοίως, ο κόμβος "3" θα επισημανθεί επίσης ως επισκέψιμος καθώς η μικρότερη απόσταση είναι 3.
Ωστόσο, αν παρατηρήσουμε, υπάρχει μια διαδρομή 1-3-2 που θα κοστίζει μόνο 2. Αλλά το Dijkstra δείχνει ότι από τον κόμβο "1" στον κόμβο "2", η μικρότερη απόσταση είναι 5. Έτσι, η Dijkstra απέτυχε να υπολογίσει τη συντομότερη απόσταση σωστά. Ο λόγος που συνέβη είναι ότι ο Dijkstra είναι ένας άπληστος αλγόριθμος. Έτσι, μόλις επισημανθεί ένας κόμβος ως επισκέψιμος, δεν θα επανεξεταστεί, αν και μπορεί να υπάρχει μια πιο σύντομη διαδρομή διαθέσιμη. Αυτό το ζήτημα παρουσιάζεται μόνο όταν οι άκρες έχουν αρνητικό κόστος ή αρνητικές άκρες βάρους
Το Dijkstra αποτυγχάνει να υπολογίσει τη συντομότερη διαδρομή μεταξύ δύο κόμβων σε αυτό το σενάριο. Ως αποτέλεσμα, αυτός ο αλγόριθμος έχει ορισμένα μειονεκτήματα. Για την επίλυση αυτού του προβλήματος των αρνητικών άκρων, χρησιμοποιείται ένας άλλος αλγόριθμος που ονομάζεται «Αλγόριθμος Bellman-Ford». Αυτός ο αλγόριθμος μπορεί να λειτουργήσει με αρνητικές ακμές.
Πολυπλοκότητα αλγορίθμου Dijkstra
Η παραπάνω υλοποίηση χρησιμοποίησε δύο βρόχους «για». Αυτοί οι βρόχοι τρέχουν για τον αριθμό των κορυφών. Άρα, η χρονική πολυπλοκότητα είναι O(V2). Εδώ, ο όρος "0" σημαίνει μια σημείωση που δίνει μια υπόθεση για τον αλγόριθμο Dijkstra.
Μπορούμε να αποθηκεύσουμε το γράφημα χρησιμοποιώντας την "Ουρά προτεραιότητας". Μια ουρά προτεραιότητας είναι μια δομή δεδομένων δυαδικού σωρού. Θα είναι πιο αποτελεσματικό από ένα 2D matrix. Μια άκρη που θα έχει ελάχιστο κόστος θα έχει υψηλή προτεραιότητα.
Τότε η χρονική πολυπλοκότητα θα είναι O (E log (V)). Εδώ, E είναι ο αριθμός των ακμών και V είναι ο αριθμός των κορυφών.
Η πολυπλοκότητα του χώρου είναι O(V2), καθώς χρησιμοποιούμε έναν πίνακα γειτνίασης (Τρισδιάστατος πίνακας). Η πολυπλοκότητα του χώρου μπορεί να βελτιστοποιηθεί χρησιμοποιώντας μια λίστα γειτνίασης ή μια δομή δεδομένων ουράς.