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

Περιγραφή

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

Στην αρχή, η απόσταση για την αρχική κορυφή θεωρείται μηδέν και οι αποστάσεις από όλες τις άλλες θεωρούνται άπειρες. Ένας πίνακας σημαιών που υποδεικνύει εάν η κορυφή έχει περάσει είναι γεμάτη με μηδενικά. Στη συνέχεια, σε κάθε βήμα του βρόχου, αναζητείται μια κορυφή με ελάχιστη απόσταση από την αρχική και μια σημαία ίση με μηδέν. Έχει οριστεί μια σημαία για αυτό και ελέγχονται όλες οι γειτονικές κορυφές. Εάν η προηγουμένως υπολογισμένη απόσταση από την κορυφή της πηγής έως την ελεγμένη κορυφή είναι μεγαλύτερη από το άθροισμα της απόστασης από την τρέχουσα κορυφή και του μήκους της άκρης από αυτήν έως την ελεγχόμενη κορυφή, τότε η απόσταση από την ελεγμένη κορυφή εξισώνεται με την απόσταση στο τρέχον + το άκρο από το τρέχον στο επιλεγμένο. Ο βρόχος τελειώνει όταν οι σημαίες όλων των κορυφών γίνονται ίσες με 1 ή όταν η απόσταση από όλες τις κορυφές με σημαία 0 είναι άπειρη. Η τελευταία περίπτωση είναι δυνατή εάν και μόνο εάν το γράφημα είναι αποσυνδεδεμένο.

Ο αλγόριθμος του Dijkstra σε ψευδοκώδικα

Είσοδος: ΑΠΟ: πίνακας πραγματικών – πίνακας μηκών τόξων γραφημάτων. s είναι η κορυφή από την οποία αναζητείται η συντομότερη διαδρομή και t είναι η κορυφή προς την οποία αναζητείται.

Έξοδος: διανύσματα T: πίνακας πραγματικών; και H: πίνακας 0..r. Αν κορυφαίο vβρίσκεται στο συντομότερο μονοπάτι από μικρόπρος την t,έπειτα Τηλεόραση]- συντομότερο μήκος διαδρομής από μικρόπρος την y; Καλά] -κορυφή αμέσως πριν στοστο συντομότερο μονοπάτι.

Το H είναι ένας πίνακας στον οποίο η κορυφή n αντιστοιχεί στην κορυφή m, η προηγούμενη στο δρόμο προς το n από το s.

Το T είναι ένας πίνακας στον οποίο η κορυφή n αντιστοιχεί στην απόσταση από αυτήν στο s.

Το X είναι ένας πίνακας στον οποίο η κορυφή n αντιστοιχεί σε 1 εάν η διαδρομή προς αυτήν είναι γνωστή, και 0 εάν όχι.

αρχικοποίηση πίνακα:

Για vαπό 1 έως Rκάνω

Τ[v]: = ∞ (άγνωστη συντόμευση)

X[v]: = 0 (όλες οι κορυφές δεν είναι επιλεγμένες)

H[s]: = 0 ( μικρό τίποτα δεν προηγείται)

T[s]:= 0 (η συντομότερη διαδρομή έχει μήκος 0...)

X[s]:= 1 (...και είναι γνωστός) v : = μικρό (τρέχουσα κορυφή)

Μ: (ενημέρωση σημειώσεων)

Για και ∈ΣΟΛ( και) κάνω

αν X[i] = 0 & T[u]> Τηλεόραση] + ντοέπειτα

T[u]: = Τηλεόραση] + ντο(βρήκε μια συντομότερη διαδρομή από μικρό σε καιδιά μέσου v }

h[u]:= v(Θυμήσου το)

Μ: = ∞

v : = 0

(βρίσκοντας το τέλος του συντομότερου μονοπατιού)

Για καιαπό 1 έως Π κάνω

αν X[u] = 0 &T[u]< tέπειτα

v:= u;

Μ:= T[u]( μπλουζα v τελειώνει το συντομότερο μονοπάτι από μικρό

αν v = 0 τότε

σταμάτα (καμία διέξοδος μικρό σε t) τέλος εαν

αν v= tέπειτα

στάση (βρήκε το συντομότερο μονοπάτι από μικρό σε t) τέλος εαν

X[v]: = 1 ( βρέθηκε η συντομότερη διαδρομή από μικρό σε v ) παω σε Μ

Λογική

Για να αποδειχθεί η ορθότητα του αλγορίθμου του Dijkstra, αρκεί να σημειωθεί ότι για κάθε εκτέλεση του σώματος του βρόχου που αρχίζει με την ετικέτα M, ως vχρησιμοποιείται μια κορυφή για την οποία είναι γνωστή η συντομότερη διαδρομή από την κορυφή μικρό.Με άλλα λόγια, αν X[v] = 1, τότε T[v] = d(s,v) , και όλες οι κορυφές στη διαδρομή (s, v) που ορίζονται από το διάνυσμα H έχουν την ίδια ιδιότητα, δηλ.

Vu T[u] = 1 => T[u] = d(s,u)&T] = 1.

Πράγματι (επαγωγικά), την πρώτη φορά ως vχρησιμοποιείται η κορυφή s, για την οποία το συντομότερο μονοπάτι είναι κενό και έχει μήκος 0 (οι μη κενές διαδρομές δεν μπορούν να είναι μικρότερες, επειδή τα μήκη τόξων είναι μη αρνητικά). Έστω T[u] = d(s,u) για όλες τις προηγουμένως επισημασμένες κορυφές και.Εξετάστε τη νέα κορυφή v, το οποίο επιλέγεται από τη συνθήκη T[v] = min T[u]. Σημειώστε ότι εάν η διαδρομή που διέρχεται από τις κορυφές με ετικέτα είναι γνωστή, τότε είναι γνωστή η συντομότερη διαδρομή. Ας υποθέσουμε (αντίθετα) ότι T[v] > d(s, v), δηλαδή το μονοπάτι που βρέθηκε που οδηγεί από μικρόσε v,δεν είναι το πιο σύντομο. Τότε πρέπει να υπάρχουν κορυφές χωρίς ετικέτα σε αυτή τη διαδρομή. Εξετάστε την πρώτη κορυφή wσε αυτό το μονοπάτι έτσι ώστε T[w] = 0.Έχουμε: T[w] = d(s,w)⩽d(s>v)< Т[v],что противоречит выбору вершины u.

Χρονική πολυπλοκότητα

Η πολυπλοκότητα του αλγορίθμου του Dijkstra εξαρτάται από τον τρόπο εύρεσης μιας κορυφής που δεν έχει επισκέψεις με την ελάχιστη απόσταση από την αρχική, τον τρόπο αποθήκευσης του συνόλου των κορυφών που δεν έχουν επισκεφτεί και τον τρόπο ενημέρωσης των ετικετών. Έστω n ο αριθμός των κορυφών και έστω m ο αριθμός των ακμών του γραφήματος. Στη συνέχεια, στην απλούστερη περίπτωση, όταν ολόκληρο το σύνολο των κορυφών αναζητείται για να βρεθεί η κορυφή με την ελάχιστη απόσταση από την αρχική κορυφή και χρησιμοποιείται ένας πίνακας για την αποθήκευση των αποστάσεων, ο χρόνος εκτέλεσης του αλγορίθμου είναι O(n 2). Ο κύριος βρόχος εκτελείται περίπου n φορές, σε καθεμία από αυτές περίπου n πράξεις δαπανώνται για την εύρεση του ελάχιστου. Η ποδηλασία μέσω των γειτόνων κάθε κορυφής που επισκέπτεστε απαιτεί έναν αριθμό πράξεων ανάλογο με τον αριθμό των ακμών m (καθώς κάθε ακμή εμφανίζεται ακριβώς δύο φορές σε αυτούς τους κύκλους και απαιτεί σταθερό αριθμό πράξεων). Έτσι, ο συνολικός χρόνος εκτέλεσης του αλγορίθμου είναι O(n 2 +m), αλλά επειδή το m είναι πολύ μικρότερο από το n(n-1), καταλήγει να είναι O(n 2).

Για αραιά γραφήματα (δηλαδή, για τα οποία το m είναι πολύ μικρότερο από το n²), οι κορυφές που δεν έχουν επισκεφτεί μπορούν να αποθηκευτούν σε έναν δυαδικό σωρό και οι τιμές απόστασης χρησιμοποιούνται ως κλειδί. Δεδομένου ότι ο βρόχος εκτελείται περίπου n φορές και ο αριθμός των χαλαρώσεων (αλλαγές ετικέτας) δεν είναι μεγαλύτερος από m, ο χρόνος εκτέλεσης μιας τέτοιας υλοποίησης είναι O(nlogn+mlogn)

Παράδειγμα

Υπολογισμός αποστάσεων από την κορυφή 1 με διασχίσιμες κορυφές:

Εξετάστε το παράδειγμα της εύρεσης του συντομότερου μονοπατιού. Δίνεται δίκτυο αυτοκινητοδρόμων που συνδέουν τις περιοχές της πόλης. Μερικοί δρόμοι είναι μονόδρομοι. Βρείτε τα συντομότερα μονοπάτια από το κέντρο της πόλης σε κάθε πόλη της περιοχής.

Για να λύσετε αυτό το πρόβλημα, μπορείτε να χρησιμοποιήσετε Ο αλγόριθμος του Dijkstra- ένας αλγόριθμος σε γραφήματα, που εφευρέθηκε από τον Ολλανδό επιστήμονα E. Dijkstra το 1959. Βρίσκει τη μικρότερη απόσταση από μια από τις κορυφές του γραφήματος σε όλες τις άλλες. Λειτουργεί μόνο για γραφήματα χωρίς ακμές αρνητικού βάρους.

Ας απαιτείται να βρεθούν οι μικρότερες αποστάσεις από την 1η κορυφή σε όλες τις άλλες.

Οι κύκλοι δηλώνουν τις κορυφές, οι γραμμές δηλώνουν τις διαδρομές μεταξύ τους (τις άκρες του γραφήματος). Οι αριθμοί των κορυφών υποδεικνύονται στους κύκλους, το βάρος τους υποδεικνύεται πάνω από τις άκρες - το μήκος της διαδρομής. Δίπλα σε κάθε κορυφή, σημειώνεται μια κόκκινη ετικέτα - το μήκος της συντομότερης διαδρομής προς αυτήν την κορυφή από την κορυφή 1.

Η ετικέτα της ίδιας της κορυφής 1 θεωρείται ότι είναι 0, οι ετικέτες των υπόλοιπων κορυφών είναι απρόσιτες μεγάλος αριθμός(ιδανικά - άπειρο). Αυτό αντανακλά ότι οι αποστάσεις από την κορυφή 1 σε άλλες κορυφές δεν είναι ακόμη γνωστές. Όλες οι κορυφές του γραφήματος επισημαίνονται ως μη επισκέψιμες.

Το πρώτο βήμα

Η κορυφή 1 έχει την ελάχιστη ετικέτα. Οι κορυφές 2, 3 και 6 είναι οι γείτονές της. Παρακάμπτουμε τους γείτονες της κορυφής με τη σειρά τους.

Ο πρώτος γείτονας της κορυφής 1 είναι η κορυφή 2 επειδή το μήκος της διαδρομής προς αυτήν είναι ελάχιστο. Το μήκος της διαδρομής προς αυτήν μέσω της κορυφής 1 είναι ίσο με το άθροισμα της μικρότερης απόστασης από την κορυφή 1, την τιμή της ετικέτας της και το μήκος της άκρης που πηγαίνει από την 1η στη 2η, δηλαδή 0 + 7 = 7. Αυτό είναι μικρότερο από την τρέχουσα ετικέτα της κορυφής 2 (10000), επομένως η νέα ετικέτα της 2ης κορυφής είναι 7.


Ομοίως, βρίσκουμε τα μήκη διαδρομής για όλους τους άλλους γείτονες (κορυφές 3 και 6).

Όλοι οι γείτονες του κόμβου 1 ελέγχονται. Η τρέχουσα ελάχιστη απόσταση μέχρι την κορυφή 1 θεωρείται οριστική και δεν υπόκειται σε αναθεώρηση. Το Vertex 1 επισημαίνεται ως επίσκεψη.

Δεύτερο βήμα

Το βήμα 1 του αλγορίθμου επαναλαμβάνεται. Και πάλι βρίσκουμε την «πλησιέστερη» από τις μη επισκέψιμες κορυφές. Αυτή είναι η κορυφή 2 με την ένδειξη 7.

Και πάλι προσπαθούμε να μειώσουμε τις ετικέτες των γειτόνων της επιλεγμένης κορυφής, προσπαθώντας να τις περάσουμε από τη 2η κορυφή. Οι γείτονες της κορυφής 2 είναι οι κορυφές 1, 3 και 4.

Το Vertex 1 έχει ήδη επισκεφθεί. Ο επόμενος γείτονας της κορυφής 2 είναι η κορυφή 3, καθώς έχει την ελάχιστη ετικέτα των κορυφών που επισημαίνονται ως μη επισκέψιμα. Εάν πάτε σε αυτό μέσω του 2, τότε το μήκος μιας τέτοιας διαδρομής θα είναι ίσο με 17 (7 + 10 = 17). Αλλά η τρέχουσα ετικέτα της τρίτης κορυφής είναι 9 και 9< 17, поэтому метка не меняется.


Ένας άλλος γείτονας της κορυφής 2 είναι η κορυφή 4. Αν πάμε σε αυτήν μέσω της 2ης, τότε το μήκος μιας τέτοιας διαδρομής θα είναι ίσο με 22 (7 + 15 = 22). Από 22<10000, устанавливаем метку вершины 4 равной 22.

Όλοι οι γείτονες της κορυφής 2 έχουν προβληθεί, επομένως το επισημαίνουμε ως επίσκεψη.

Τρίτο βήμα

Επαναλαμβάνουμε το βήμα του αλγορίθμου επιλέγοντας την κορυφή 3. Μετά την «επεξεργασία» του, έχουμε τα ακόλουθα αποτελέσματα.

Τέταρτο βήμα

Πέμπτο βήμα

έκτο βήμα

Έτσι, η συντομότερη διαδρομή από την κορυφή 1 έως την κορυφή 5 θα είναι η διαδρομή μέσω των κορυφών 1 — 3 — 6 — 5 , αφού με αυτόν τον τρόπο παίρνουμε ελάχιστο βάρος 20.

Ας ρίξουμε μια ματιά στο συντομότερο μονοπάτι. Γνωρίζουμε το μήκος της διαδρομής για κάθε κορυφή, και τώρα θα εξετάσουμε τις κορυφές από το τέλος. Εξετάστε την τελική κορυφή (σε αυτήν την περίπτωση, την κορυφή 5 ), και για όλες τις κορυφές με τις οποίες συνδέεται, βρίσκουμε το μήκος διαδρομής αφαιρώντας το βάρος της αντίστοιχης ακμής από το μήκος διαδρομής της τελικής κορυφής.
Ναι, κορυφαίο 5 έχει μήκος διαδρομής 20 . Είναι συνδεδεμένη με την κορυφή 6 και 4 .
Για την κορυφή 6 πάρε το βάρος 20 - 9 = 11 (ταιριάζουν).
Για την κορυφή 4 πάρε το βάρος 20 - 6 = 14 (δεν ταίριαξε).
Εάν ως αποτέλεσμα λάβουμε μια τιμή που ταιριάζει με το μήκος διαδρομής της εν λόγω κορυφής (στην περίπτωση αυτή, η κορυφή 6 ), τότε ήταν από αυτό που έγινε η μετάβαση στην τελική κορυφή. Σημειώνουμε αυτή την κορυφή στην επιθυμητή διαδρομή.
Στη συνέχεια, προσδιορίζουμε την άκρη μέσω της οποίας φτάσαμε στην κορυφή 6 . Και ούτω καθεξής μέχρι να φτάσουμε στην αρχή.
Εάν, ως αποτέλεσμα μιας τέτοιας διέλευσης, σε κάποιο βήμα έχουμε τις ίδιες τιμές για πολλές κορυφές, τότε μπορούμε να πάρουμε οποιαδήποτε από αυτές - πολλά μονοπάτια θα έχουν το ίδιο μήκος.

Υλοποίηση του αλγορίθμου του Dijkstra

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

	1	2	3	4	5	6
1	0	7	9	0	0	14
2	7	0	10	15	0	0
3	9	10	0	11	0	2
4	0	15	11	0	6	0
5	0	0	0	6	0	9
6	14	0	2	0	9	0

Υλοποίηση σε C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

#define _CRT_SECURE_NO_WARNINGS
#περιλαμβάνω
#περιλαμβάνω
#define SIZE 6
int main()
{
int a? // μήτρα συνδέσεων
int d; // ελάχιστη απόσταση
intv? // επισκέψεις κορυφές
int temp, miniindex, min;
int start_index = 0;
system("chcp 1251" );
system("cls" );
// Αρχικοποίηση του πίνακα σχέσεων
για (int i = 0; i {
a[i][i] = 0;
για (int j = i + 1; j printf( "Εισαγάγετε απόσταση %d - %d: ", i + 1, j + 1);
scanf("%d" , &temp);
a[i][j] = θερμοκρασία;
a[j][i] = θερμοκρασία;
}
}
// Εμφάνιση του πίνακα σχέσεων
για (int i = 0; i {
για (int j = 0; j printf("%5d " , a[i][j]);
printf("\n");
}
//Αρχικοποίηση κορυφών και αποστάσεων
για (int i = 0; i {
d[i] = 10000;
v[i] = 1;
}
d=0;
// Βήμα αλγορίθμου
κάνω(
minindex = 10000;
min = 10000;
για (int i = 0; i { // Εάν δεν έχει γίνει ακόμη επίσκεψη στην κορυφή και το βάρος είναι μικρότερο από min
εάν ((v[i] == 1) && (d[i] { // Εκ νέου εκχώρηση τιμών
min = d[i];
miniindex=i;
}
}
// Προσθέστε το ελάχιστο βάρος που βρέθηκε
// στο τρέχον βάρος κορυφής
// και συγκρίνετε με το τρέχον ελάχιστο βάρος κορυφής
εάν (ελάχιστος δείκτης != 10000)
{
για (int i = 0; i {
εάν (a[i] > 0)
{
temp = min + a[i];
εάν (θερμ< d[i])
{
d[i] = θερμοκρασία;
}
}
}
v = 0;
}
) ενώ (minindex< 10000);
// Εμφάνιση των μικρότερων αποστάσεων από τις κορυφές
printf( "\nΜικρότερες αποστάσεις από κορυφές: \n");
για (int i = 0; i printf("%5d " , d[i]);

// Επαναφορά διαδρομής
inverver? // πίνακας επισκέψεων κορυφών
int end = 4; // δείκτης τελικής κορυφής = 5 - 1
ver = τέλος + 1; // στοιχείο έναρξης - κορυφή κορυφής
int k = 1; // δείκτης της προηγούμενης κορυφής
int βάρος = d; // βάρος κορυφής άκρου

ενώ (τέλος != start_index) // μέχρι να φτάσουμε στην αρχική κορυφή
{
για (int i = 0; i // κοιτάξτε όλες τις κορυφές
αν (a[i] != 0) // εάν υπάρχει σύνδεση
{
int temp = βάρος - a[i]; // προσδιορίστε το βάρος της διαδρομής από την προηγούμενη κορυφή
εάν (θερμοκρασία == d[i]) // εάν το βάρος ταιριάζει με το υπολογισμένο
{ // σημαίνει ότι υπήρξε μετάβαση από αυτήν την κορυφή
βάρος = θερμοκρασία; // αποθηκεύστε το νέο βάρος
τέλος = i; // αποθήκευση της προηγούμενης κορυφής
ver[k] = i + 1; // και γράψτε το σε έναν πίνακα
k++;
}
}
}
// Εμφάνιση της διαδρομής (η αρχική κορυφή βρίσκεται στο τέλος του πίνακα των k στοιχείων)
printf( "\nΈξοδος συντομότερη διαδρομή\n");
για (int i = k - 1; i >= 0; i--)
printf("%3d " , ver[i]);
getchar(); getchar();
επιστροφή 0;
}

Αποτέλεσμα εκτέλεσης


Πίσω:

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

Αυτό το πρόβλημα ονομάζεται πρόβλημα συντομότερων διαδρομών μίας πηγής.

Αλγόριθμος

Αυτό περιγράφει τον αλγόριθμο που προτείνει ο Ολλανδός ερευνητής Dijkstra(Dijkstra) το 1959

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

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

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

(Είναι σαφές ότι στην πρώτη επανάληψη θα επιλεγεί η αρχική κορυφή.)

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

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

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

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

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

Απόδειξη

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

Απόδειξηθα παράγουμε επαγωγικά. Για την πρώτη επανάληψη, η εγκυρότητά της είναι προφανής - για την κορυφή που έχουμε , η οποία είναι το μήκος της συντομότερης διαδρομής προς αυτήν. Τώρα ας ισχύει αυτός ο ισχυρισμός για όλες τις προηγούμενες επαναλήψεις, δηλ. όλες οι ήδη σημειωμένες κορυφές. ας αποδείξουμε ότι δεν παραβιάζεται μετά την εκτέλεση της τρέχουσας επανάληψης. Έστω η κορυφή που επιλέχθηκε στην τρέχουσα επανάληψη, δηλ. την κορυφή που πρόκειται να επισημάνει ο αλγόριθμος. Ας αποδείξουμε ότι είναι πραγματικά ίσο με το μήκος του συντομότερου μονοπατιού προς αυτό (συμβολίζουμε αυτό το μήκος με ).

Εξετάστε το συντομότερο μονοπάτι προς την κορυφή. Είναι σαφές ότι αυτή η διαδρομή μπορεί να χωριστεί σε δύο μονοπάτια: , που αποτελείται μόνο από σημειωμένες κορυφές (τουλάχιστον η αρχική κορυφή θα είναι σε αυτήν τη διαδρομή) και την υπόλοιπη διαδρομή (μπορεί επίσης να περιλαμβάνει σημειωμένες κορυφές, αλλά ξεκινά πάντα με ένα ασήμαντο). Σημειώστε με την πρώτη κορυφή της διαδρομής και με την τελευταία κορυφή της διαδρομής.

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

Λόγω του μη αρνητικού κόστους των ακμών, το μήκος της συντομότερης διαδρομής (που, σύμφωνα με όσα μόλις αποδείχθηκε, ισούται με ) δεν υπερβαίνει το μήκος της συντομότερης διαδρομής προς την κορυφή . Λαμβάνοντας υπόψη ότι (εξάλλου, ο αλγόριθμος του Dijkstra δεν μπορούσε να βρει μια συντομότερη διαδρομή από ό, τι είναι γενικά δυνατό), ως αποτέλεσμα, λαμβάνουμε τις ακόλουθες σχέσεις:

Από την άλλη πλευρά, δεδομένου ότι και τα δύο και και είναι κορυφές χωρίς ετικέτα, δεδομένου ότι ήταν η κορυφή που επιλέχθηκε στην τρέχουσα επανάληψη, και όχι η κορυφή , λαμβάνουμε μια άλλη ανισότητα:

Από αυτές τις δύο ανισότητες συμπεραίνουμε την ισότητα , και στη συνέχεια από τις σχέσεις που βρέθηκαν προηγουμένως, παίρνουμε και:

Q.E.D.

Εκτέλεση

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

Ο χρόνος εκτέλεσης του αλγορίθμου είναι το άθροισμα:

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

Εκτέλεση:

const int INF = 1000000000 ; int main() ( int n; ... read n ... διάνυσμα< vector < pair< int ,int >> > g(n); ... ανάγνωση γραφήματος... int s = ...; // κορυφή αρχήςδιάνυσμα< int >d(n, INF) , p(n) ; d[s] = 0; διάνυσμα< char >Ηνωμένα Έθνη); για (int i= 0 ; i< n; ++ i) { int v = - 1 ; for (int j= 0 ; j< n; ++ j) if (! u[ j] && (v == - 1 || d[ j] < d[ v] ) ) v = j; if (d[ v] == INF) break ; u[ v] = true ; for (size_t j= 0 ; j< g[ v] .size () ; ++ j) { int to = g[ v] [ j] .first , len = g[ v] [ j] .second ; if (d[ v] + len < d[ to] ) { d[ to] = d[ v] + len; p[ to] = v; } } } }

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

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

Ας δοθεί ένα δίγραμμα σολ(V, μι), σε κάθε τόξο του οποίου εκχωρείται ένας αριθμός
που ονομάζεται μήκος τόξου.

Ορισμός. Μήκοςδιαδρομή είναι το άθροισμα των μηκών των τόξων που απαρτίζουν αυτή τη διαδρομή. Πρόβλημα συντομότερης διαδρομήςβάλε έτσι.

Επιλογή 1.Βρείτε τα μήκη των συντομότερων μονοπατιών (μονοπάτια ελάχιστου μήκους) και τα ίδια τα μονοπάτια από μια σταθερή κορυφή μικρόσε όλες τις άλλες κορυφές του γραφήματος.

Επιλογή 2.Βρείτε τα μήκη των συντομότερων μονοπατιών και τα ίδια τα μονοπάτια μεταξύ όλων των ζευγών κορυφών στο δεδομένο γράφημα.

Εάν το γράφημα έχει τόξα αρνητικού μήκους, το πρόβλημα μπορεί να μην έχει λύσεις (θα χάσει το νόημά του). Αυτό οφείλεται στο γεγονός ότι το γράφημα μπορεί να περιέχει ένα περίγραμμα αρνητικού μήκους. Η παρουσία περιγραμμάτων αρνητικού μήκους σημαίνει ότι το μήκος της διαδρομής μπορεί να γίνει ίσο με
. Και αν δεν υπάρχουν περιγράμματα αρνητικού μήκους, τότε υπάρχουν τα συντομότερα μονοπάτια και κάθε συντομότερο μονοπάτι είναι μια απλή αλυσίδα.

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

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

Ο αλγόριθμος λειτουργεί με τόξα θετικού μήκους και καθορίζει τις συντομότερες διαδρομές από μια σταθερή κορυφή μικρόσε όλες τις άλλες κορυφές του γραφήματος. Ας χαρακτηρίσουμε αυτές τις κορυφές v 1 , v 2 ,…, v n .

Ορισμός.Ας ονομάσουμε την κορυφή uπου βρίσκεται πιο κοντά στην κορυφή μικρόπαρά πάνω vαν το μήκος της συντομότερης διαδρομής από μικρόπριν uμικρότερο από το μήκος της συντομότερης διαδρομής από μικρόπριν v. Θα πούμε ότι οι κορυφές uκαι v αυτός που απέχει εξίσουΑπο πάνω μικρό, εάν τα μήκη των συντομότερων μονοπατιών από μικρόπριν uκαι από μικρόπριν vαγώνας.

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

Αν τα μήκη τόξων είναι θετικοί αριθμοί, τότε

πιο κοντά στο μικρό η κορυφή είναι ο εαυτός της. Το μήκος της συντομότερης διαδρομής από μικρόπριν μικρόείναι 0;

πιο κοντά στο μικρό κορυφή εκτός από μικρό, ψέματα από μικρόσε απόσταση ενός τόξου - το μικρότερο από όλα τα τόξα που αναδύονται από την κορυφή μικρό;

οποιαδήποτε ενδιάμεση κορυφή της συντομότερης διαδρομής από μικρόμέχρι κάποια κορυφή vβρίσκεται πιο κοντά στο μικρόαπό την τελική κορυφή v;

η συντομότερη διαδρομή προς την επόμενη διατεταγμένη κορυφή μπορεί να περάσει μόνο από ήδη διατεταγμένες κορυφές.

Αφήστε τον αλγόριθμο να έχει ήδη διατάξει τις κορυφές v 1 , v 2 … v κ . Σημειώστε με
,
μήκος της συντομότερης διαδρομής προς την κορυφή v Εγώ .

Εξετάστε όλα τα τόξα του αρχικού γραφήματος που ξεκινούν σε μία από τις κορυφές του συνόλου
και τελειώνουν σε ακόμη αδιάτακτες κορυφές. Για κάθε τέτοιο τόξο, για παράδειγμα
, υπολογίστε το άθροισμα
. Αυτό το άθροισμα ισούται με το μήκος της διαδρομής από μικρό σε y, στην οποία η κορυφή v Εγώείναι η προτελευταία κορυφή, και η διαδρομή από μικρό σε v Εγώείναι το συντομότερο από όλα τα μονοπάτια που συνδέουν μικρό και v Εγώ .

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

Τεχνικά, οι ενέργειες σύμφωνα με τον αλγόριθμο του Dijkstra εκτελούνται χρησιμοποιώντας τη συσκευή των ετικετών κορυφής. Ετικέτα Vertex vσυμβολίζεται ως
. Κάθε ετικέτα είναι ένας αριθμός ίσος με το μήκος κάποιας διαδρομής από μικρό πριν v. Οι ετικέτες χωρίζονται σε προσωρινές και μόνιμες. Σε κάθε βήμα, μόνο μία ετικέτα γίνεται μόνιμη. Αυτό σημαίνει ότι η τιμή του είναι ίση με το μήκος της συντομότερης διαδρομής προς την αντίστοιχη κορυφή, και αυτή η ίδια η κορυφή είναι διατεταγμένη. Ο αριθμός της επόμενης διατεταγμένης κορυφής συμβολίζεται με το γράμμα R.

Περιγραφή του αλγορίθμου.

Βήμα 1. (Αρχική ρύθμιση). Βάζω
και θεωρήστε αυτή την ετικέτα μόνιμη. Βάζω
,
και να αντιμετωπίζετε αυτές τις ετικέτες ως προσωρινές. Βάζω
.

Βήμα 2 (γενικό βήμα).Επαναλαμβάνεται n φορές μέχρι να ταξινομηθούν όλες οι κορυφές του γραφήματος.

Υπολογίστε ξανά τη χρονική σήμανση
οποιαδήποτε αδιάτακτη κορυφή v Εγώ, που περιλαμβάνει το τόξο που εξέρχεται από την κορυφή R,σύμφωνα με τον κανόνα

Επιλέξτε την κορυφή με την ελάχιστη χρονική σήμανση. Εάν υπάρχουν πολλές τέτοιες κορυφές, επιλέξτε οποιαδήποτε.

Αφήνω w- την κορυφή με την ελάχιστη χρονική σήμανση. Σημάδι ανάγνωσης
σταθερό και βάλε
.

Είναι βολικό να τακτοποιήσετε τα βήματα του αλγορίθμου του Dijkstra σε έναν πίνακα, κάθε στήλη του οποίου αντιστοιχεί σε μια κορυφή του γραφήματος. Οι σειρές του πίνακα αντιστοιχούν στην επανάληψη του κοινού βήματος.

Παράδειγμα. Για το γράφημα στο Σχ. 4. βρείτε τα συντομότερα μονοπάτια από τις κορυφές
σε όλες τις άλλες κορυφές του γραφήματος. Τα άκρα σημαίνουν δύο διαφορετικά κατευθυνόμενα τόξα του ίδιου μήκους.

Λύση.Στον πίνακα. Γράφονται 1 ετικέτες κορυφών σε κάθε βήμα. Τα μόνιμα σημάδια σημειώνονται με το σύμβολο "+". Ας περιγράψουμε λεπτομερώς πώς υπολογίζονται οι ετικέτες κορυφής.

Από την κορυφή 1, τα τόξα βγαίνουν στις κορυφές 2, 5, 6. Υπολογίστε ξανά τις ετικέτες αυτών των κορυφών και συμπληρώστε τη δεύτερη σειρά του πίνακα.

Η ετικέτα Vertex 6 γίνεται μόνιμη,
.

Από την κορυφή 6, τα τόξα βγαίνουν στις ακόμα μη ταξινομημένες κορυφές 2, 5, 8, 9. Υπολογίστε ξανά τις χρονικές τους σημάνσεις

Συμπληρώστε τη σειρά 3 του πίνακα. Το ελάχιστο των χρονικών σημάνσεων είναι 3 (ετικέτα κορυφής 9),
.

Από την κορυφή 9, τα τόξα βγαίνουν στις ακόμα μη διατεταγμένες κορυφές 5, 8, 11, 12. Στη συνέχεια

Συμπληρώστε την τέταρτη γραμμή του πίνακα. Σε αυτή τη γραμμή, δύο κορυφές - 2 και 12 έχουν ελάχιστες χρονικές σημάνσεις ίσες με 4. Αρχικά, ας παραγγείλουμε, για παράδειγμα, την κορυφή 2. Στη συνέχεια, στο επόμενο βήμα, θα ταξινομηθεί η κορυφή 12.

Τραπέζι 1

Ετσι,
.

Από την κορυφή 2, τα τόξα βγαίνουν στις ακόμα μη διατεταγμένες κορυφές 3, 4, 5. Υπολογίστε ξανά τις χρονικές σημάνσεις αυτών των κορυφών

Συμπληρώστε τη σειρά 5 του πίνακα. Το ελάχιστο των χρονικών σημάνσεων είναι 4 (ετικέτα κορυφής 12),
.

Συμπληρώστε τη σειρά 6 του πίνακα. Το ελάχιστο των χρονικών σημάνσεων είναι 5 (ετικέτα κορυφής 5),
.

Συμπληρώστε τη σειρά 7 του πίνακα. Η ετικέτα κορυφής 8 γίνεται σταθερή (ισούται με 5),
.

Το Vertex 11 έχει παραγγελθεί.

Από την κορυφή 11, τα τόξα βγαίνουν στις μη διατεταγμένες κορυφές 7, 10. Υπολογίστε ξανά τις χρονικές σημάνσεις αυτών των κορυφών

Το Vertex 4 παίρνει μια μόνιμη ετικέτα.

Από την κορυφή 4, τα τόξα βγαίνουν στις μη ταξινομημένες κορυφές 3, 7. Υπολογίστε ξανά τις χρονικές σημάνσεις

Τακτοποιήστε την κορυφή 3.

Συμπληρώστε τη γραμμή 12 του πίνακα. Σε αυτό το βήμα, διατάσσουμε την τελευταία μη διατεταγμένη κορυφή 10.

Χτίζοντας ένα δέντρο με τα συντομότερα μονοπάτια.

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

Το δέντρο της συντομότερης διαδρομής κατασκευάζεται σύμφωνα με τον πίνακα, κορυφή προς κορυφή περιλαμβάνεται σε αυτό με τη σειρά με την οποία έλαβαν μόνιμες ετικέτες. Η ρίζα είναι ο πρώτος κόμβος που περιλαμβάνεται στο δέντρο. μικρό .

Ας φτιάξουμε ένα δέντρο με τα συντομότερα μονοπάτια για το παράδειγμά μας.

Αρχικά, συμπεριλαμβάνουμε τη ρίζα, κορυφή 1, στο δέντρο. Στη συνέχεια, το τόξο (1,6) περιλαμβάνεται στο δέντρο. Στη συνέχεια διατάχθηκε η κορυφή 9, το μήκος της συντομότερης διαδρομής προς την οποία είναι ίσο με 3. Την πρώτη φορά εμφανίστηκε ο αριθμός 3 στην τρίτη σειρά, η οποία ήταν γεμάτη
. Επομένως, η κορυφή 6 είναι η προτελευταία κορυφή της συντομότερης διαδρομής προς την κορυφή 9. Περιλαμβάνουμε το τόξο (6,9) μήκους 1 στο δέντρο.

Στη συνέχεια, η κορυφή 2 ταξινομήθηκε με το μικρότερο μήκος διαδρομής ίσο με 4. Αυτός ο αριθμός εμφανίστηκε για πρώτη φορά στην τρίτη σειρά, η οποία συμπληρώθηκε με
. Κατά συνέπεια, η συντομότερη διαδρομή προς τη δεύτερη κορυφή διέρχεται κατά μήκος του τόξου (6,2). Περιλαμβάνουμε το τόξο (6,2) μήκους 2 στο δέντρο.

Στη συνέχεια, διατάχθηκε η κορυφή 12,
. Την πρώτη φορά εμφανίζεται ο αριθμός 4 στην τέταρτη γραμμή, η οποία συμπληρώθηκε πότε
. Στο δέντρο περιλαμβάνεται το τόξο (9,12) μήκους 1. Το πλήρες δέντρο των συντομότερων μονοπατιών φαίνεται στο σχ. 5.

Ο αλγόριθμος του Dijkstra μπορεί να αποτύχει εάν το γράφημα έχει τόξα αρνητικού μήκους. Έτσι, αναζητώντας τα συντομότερα μονοπάτια από την κορυφή μικρό =1 για το γράφημα στο σχ. 6, ο αλγόριθμος θα παραγγείλει πρώτα τον κόμβο 3, μετά τον κόμβο 2 και θα ολοκληρώσει. Επιπλέον, αυτή η συντομότερη διαδρομή προς την κορυφή 3, από την άποψη του αλγόριθμου του Dijkstra, είναι ένα τόξο (1,3) μήκους 3.

Στην πραγματικότητα, η συντομότερη διαδρομή προς την κορυφή 3 αποτελείται από τόξα (1,2) και (2,3), το μήκος αυτής της διαδρομής είναι 5+(-3)=2.

Λόγω της παρουσίας τόξου (2,3) αρνητικού μήκους –3, παραβιάστηκαν οι ακόλουθες βασικές αρχές:

πιο κοντά στο μικρό η κορυφή βρίσκεται σε απόσταση δύο τόξων από αυτήν και όχι ενός.

η ενδιάμεση κορυφή της συντομότερης διαδρομής 1-2-3 (κορυφή 2) βρίσκεται πιο μακριά από την κορυφή 1 (απόσταση 5) από την τελική κορυφή της διαδρομής 3.

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

Από τους πολλούς αλγόριθμους για την εύρεση των συντομότερων διαδρομών σε ένα γράφημα, στο Habré βρήκα μόνο μια περιγραφή του αλγορίθμου Floyd-Warshall. Αυτός ο αλγόριθμος βρίσκει τα συντομότερα μονοπάτια μεταξύ όλων των κορυφών του γραφήματος και του μήκους τους. Σε αυτό το άρθρο, θα περιγράψω την αρχή λειτουργίας του αλγόριθμου του Dijkstra, ο οποίος βρίσκει τις βέλτιστες διαδρομές και το μήκος τους μεταξύ μιας συγκεκριμένης κορυφής (πηγή) και όλων των άλλων κορυφών του γραφήματος. Το μειονέκτημα αυτού του αλγορίθμου είναι ότι δεν θα λειτουργήσει σωστά εάν το γράφημα έχει τόξα αρνητικού βάρους.

Για παράδειγμα, πάρτε το ακόλουθο κατευθυνόμενο γράφημα G:

Μπορούμε να αναπαραστήσουμε αυτό το γράφημα ως πίνακα C:

Ας πάρουμε ως πηγή την κορυφή 1. Αυτό σημαίνει ότι θα αναζητήσουμε τις συντομότερες διαδρομές από την κορυφή 1 έως τις κορυφές 2, 3, 4 και 5.
Αυτός ο αλγόριθμος επαναλαμβάνεται βήμα προς βήμα σε όλες τις κορυφές του γραφήματος και τους αποδίδει ετικέτες, οι οποίες είναι η γνωστή ελάχιστη απόσταση από την κορυφή της πηγής σε μια συγκεκριμένη κορυφή. Ας εξετάσουμε αυτόν τον αλγόριθμο με ένα παράδειγμα.

Ας αντιστοιχίσουμε μια ετικέτα ίση με 0 στην 1η κορυφή, γιατί αυτή η κορυφή είναι η πηγή. Στις υπόλοιπες κορυφές θα εκχωρηθούν ετικέτες ίσες με το άπειρο.

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

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

Επιλέγουμε την κορυφή 2. Αλλά δεν υπάρχει εξερχόμενη διαδρομή από αυτήν, οπότε επισημαίνουμε αμέσως αυτήν την κορυφή ως επισκέψιμη και προχωράμε στην επόμενη κορυφή με την ελάχιστη ετικέτα. Αυτή τη φορά μόνο η κορυφή 5 έχει την ελάχιστη ετικέτα. Εξετάστε όλες τις κορυφές προς τις οποίες υπάρχουν άμεσες διαδρομές από το 5, αλλά οι οποίες δεν έχουν ακόμη επισημανθεί ως επισκέψιμες. Βρίσκουμε πάλι το άθροισμα της ετικέτας της κορυφής W και το βάρος της ακμής από το W στην τρέχουσα κορυφή, και αν αυτό το άθροισμα είναι μικρότερο από την προηγούμενη ετικέτα, τότε αντικαθιστούμε την τιμή της ετικέτας με το άθροισμα που προκύπτει.

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

Αφού ολοκληρώσουμε όλα τα βήματα, έχουμε το ακόλουθο αποτέλεσμα:

Υπάρχει επίσης ένα διάνυσμα P, βάσει του οποίου μπορείτε να δημιουργήσετε τις συντομότερες διαδρομές. Με τον αριθμό των στοιχείων, αυτό το διάνυσμα είναι ίσο με τον αριθμό των κορυφών του γραφήματος Κάθε στοιχείο περιέχει την τελευταία ενδιάμεση κορυφή στη συντομότερη διαδρομή μεταξύ της κορυφής πηγής και της τελικής κορυφής. Στην αρχή του αλγορίθμου, όλα τα στοιχεία του διανύσματος P είναι ίσα με την κορυφή της πηγής (στην περίπτωσή μας, P = (1, 1, 1, 1, 1)). Επιπλέον, στο στάδιο του επανυπολογισμού της τιμής της ετικέτας για την εξεταζόμενη κορυφή, εάν η ετικέτα της εξεταζόμενης κορυφής αλλάξει σε μικρότερη, γράφουμε την τιμή της τρέχουσας κορυφής W στον πίνακα P. Για παράδειγμα: η 3η κορυφή είχε μια ετικέτα με την τιμή "30", με W=1. Επιπλέον, στο W=5, η ετικέτα της 3ης κορυφής έχει αλλάξει σε "20", επομένως θα γράψουμε την τιμή στο διάνυσμα P - P=5. Επίσης, στο W=5, η τιμή της ετικέτας στην 4η κορυφή έχει αλλάξει (ήταν "50", έγινε "40"), επομένως πρέπει να αντιστοιχίσετε την τιμή W - P=5 στο 4ο στοιχείο του διάνυσμα Π. Ως αποτέλεσμα, παίρνουμε το διάνυσμα Р = (1, 1, 5, 5, 1).

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