Εξετάστε το παράδειγμα της εύρεσης του συντομότερου μονοπατιού. Δίνεται δίκτυο αυτοκινητοδρόμων που συνδέουν τις περιοχές της πόλης. Μερικοί δρόμοι είναι μονόδρομοι. Βρείτε τα συντομότερα μονοπάτια από το κέντρο της πόλης σε κάθε πόλη της περιοχής.
Για να λύσετε αυτό το πρόβλημα, μπορείτε να χρησιμοποιήσετε Ο αλγόριθμος του 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
scanf("%d" , &temp);
a[i][j] = θερμοκρασία;
a[j][i] = θερμοκρασία;
}
}
// Εμφάνιση του πίνακα σχέσεων
για (int i = 0; i
για (int j = 0; j
printf("\n");
}
//Αρχικοποίηση κορυφών και αποστάσεων
για (int i = 0; i
d[i] = 10000;
v[i] = 1;
}
d=0;
// Βήμα αλγορίθμου
κάνω(
minindex = 10000;
min = 10000;
για (int i = 0; i
εάν ((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
// Επαναφορά διαδρομής
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 είναι ένας αλγόριθμος γραφήματος που εφευρέθηκε από τον Ολλανδό επιστήμονα E. Dijkstra το 1959. Βρίσκει τη μικρότερη απόσταση από μια από τις κορυφές του γραφήματος σε όλες τις άλλες. Ο αλγόριθμος λειτουργεί μόνο για γραφήματα χωρίς ακμές αρνητικού βάρους. Ο αλγόριθμος είναι χρησιμοποιείται ευρέως στον προγραμματισμό και τεχνολογίες όπως το OSPF το χρησιμοποιεί για την εξάλειψη των δρομολογίων επαναφοράς, γνωστές και ως Πρώτη Συντομότερη Διαδρομή.
Ο αλγόριθμος του Dijkstra λύνει το πρόβλημα της συντομότερης διαδρομής μιας κορυφής για ένα σταθμισμένο κατευθυνόμενο γράφημα G = (V, E) με αρχική κορυφή s, στο οποίο τα βάρη όλων των ακμών είναι μη αρνητικά ((u, v) ? 0 για όλα (u , v) Ε). Στην περίπτωση που οι άκρες του γραφήματος δεν είναι ίσες, συνιστάται να χρησιμοποιήσετε αυτόν τον αλγόριθμο.
Διατύπωση εργασίας.Υπάρχει ένα γράφημα. Ορισμένες από τις κορυφές του ορίζονται ως κορυφή 1. Είναι απαραίτητο να βρεθούν οι ελάχιστες διαδρομές από την κορυφή 1 σε κάθε μια από τις κορυφές του γραφήματος. Η ελάχιστη διαδρομή είναι η διαδρομή με το ελάχιστο άθροισμα τιμών κατά μήκος της διαδρομής. Η τιμή είναι ένας μη αρνητικός αριθμός που είναι το βάρος της άκρης.
Η ιδέα του αλγορίθμου.Η ιδέα βασίζεται στην ακόλουθη προφανή πρόταση: Αφήστε την ελάχιστη διαδρομή από την κορυφή έναστην κορυφή Β. Και έστω η κορυφή Β συνδέεται με κάποιο αριθμό κορυφών i . Να συμβολίσετε με C i το κόστος της διαδρομής από την κορυφή Β στην κορυφή i. Ας επιλέξουμε την ελάχιστη τιμή από το C i. Τότε η ελάχιστη συνέχεια της διαδρομής από το σημείο Β θα περάσει από την επιλεγμένη τιμή.
Αυτή η δήλωση δεν απαιτεί πραγματικά απόδειξη. Και από αυτό προκύπτει μια πολύ σοβαρή συνέπεια. Ας υπάρχει ένα σύνολο κορυφών από τις οποίες ήδη περνούν ελάχιστες διαδρομές. Ένα τέτοιο σύνολο είναι εγγυημένο ότι υπάρχει, αυτή είναι η κορυφή 1. Η δήλωση που διατυπώθηκε παραπάνω καθιστά δυνατή την προσθήκη μιας ακόμη κορυφής στο ήδη υπάρχον σύνολο κορυφών (θα τις ονομάσουμε περαιτέρω επιλεγμένες) και δεδομένου ότι ο αριθμός των κορυφών στο γράφημα είναι πεπερασμένο, τότε σε έναν πεπερασμένο αριθμό βημάτων θα επιλεγούν όλες οι κορυφές του γραφήματος και αυτή θα είναι η λύση.
Η ουσία του αλγορίθμου του Dijkstra είναι η διαδικασία για την προσθήκη μιας ακόμη κορυφής στο σύνολο των επιλεγμένων. Αυτή η διαδικασία αποτελείται από δύο βήματα:
1. Κατασκευάζουμε ένα σύνολο κορυφών που προσπίπτουν στην επιλεγμένη και βρίσκουμε ανάμεσά τους την κορυφή με τη χαμηλότερη τιμή. Η κορυφή που βρέθηκε προστίθεται στο σύνολο των επιλεγμένων.
2. Κατασκευάζουμε ένα σύνολο κορυφών που προσπίπτουν στην επιλεγμένη και καθορίζουμε νέες τιμές για αυτές. Η νέα τιμή μιας κορυφής είναι το ελάχιστο κόστος της διαδρομής από το σύνολο των επιλεγμένων κορυφών στη δεδομένη κορυφή. Η νέα τιμή είναι κατασκευασμένη ως εξής:
ένα. Για μια μη επιλεγμένη κορυφή στο σύνολο των επιλεγμένων κορυφών, προσδιορίζεται ένα υποσύνολο κορυφών που προσπίπτουν σε αυτήν.
σι. Για κάθε κορυφή του επιλεγμένου υποσυνόλου προσδιορίζεται το κόστος της διαδρομής προς τη δεδομένη.
ντο. Καθορίζεται η ελάχιστη τιμή. Αυτή η τιμή γίνεται η κορυφαία τιμή.
Ο αλγόριθμος λειτουργεί με δύο τύπους τιμών: τιμή αιχμής και κορυφαία τιμή. Οι ακραίες τιμές είναι σταθερές. Οι τιμές των κορυφών επανυπολογίζονται συνεχώς. Το νόημα αυτών των τιμών είναι διαφορετικό. Το κόστος μιας ακμής είναι το κόστος μετακίνησης από μια κορυφή σε μια κορυφή που συνδέεται με αυτήν την ακμή. Και η τιμή της κορυφής είναι η τιμή της ελάχιστης διαδρομής. Μια άλλη σημαντική σημείωση αφορά τον επανυπολογισμό των προκαταρκτικών τιμών. Στην πραγματικότητα, είναι λογικό να υπολογίζουμε εκ νέου τις προκαταρκτικές τιμές μόνο για εκείνες τις κορυφές που σχετίζονται με την κορυφή που προστέθηκε στο σύνολο των επιλεγμένων στο τελευταίο βήμα, καθώς για άλλες κορυφές δεν υπάρχει λόγος αλλαγής της προκαταρκτικής τιμής.
Είναι γνωστό ότι όλες οι τιμές (για παράδειγμα, η τοποθέτηση μονοπατιού ή περάσματος) είναι μη αρνητικές. Βρείτε τη διαδρομή ελάχιστου κόστους 1->i για όλα τα i=1. n σε χρόνο O(n2).
Κατά τη λειτουργία του αλγορίθμου, θα επιλεγούν ορισμένες πόλεις (στην αρχή - μόνο πόλη 1, στο τέλος - όλες). Εν:
Για κάθε επιλεγμένη πόλη i, αποθηκεύεται το ελάχιστο κόστος της διαδρομής 1->i. Ταυτόχρονα, είναι γνωστό ότι το ελάχιστο επιτυγχάνεται στο μονοπάτι που διέρχεται μόνο από επιλεγμένες πόλεις.
για κάθε μη κατανεμημένη πόλη i, αποθηκεύεται το ελάχιστο κόστος της διαδρομής 1->i, στην οποία μόνο οι επιλεγμένες πόλεις χρησιμοποιούνται ως ενδιάμεσες.
Το σύνολο των κατανεμημένων πόλεων επεκτείνεται με βάση την ακόλουθη παρατήρηση: εάν μεταξύ όλων των μη κατανεμημένων πόλεων πάρουμε αυτή για την οποία ο αποθηκευμένος αριθμός είναι ελάχιστος, τότε αυτός ο αριθμός είναι το πραγματικό ελάχιστο κόστος. Πράγματι, ας υπάρχει πιο σύντομος δρόμος. Σκεφτείτε την πρώτη μη επιλεγμένη πόλη σε αυτό το μονοπάτι - η διαδρομή προς αυτήν είναι ήδη μεγαλύτερη! (Η αρνητικότητα των τιμών είναι απαραίτητη εδώ.)
Προσθέτοντας την επιλεγμένη πόλη στις επιλεγμένες, πρέπει να διορθώσουμε τις πληροφορίες που είναι αποθηκευμένες για τις μη επιλεγμένες πόλεις. Σε αυτήν την περίπτωση, αρκεί να ληφθούν υπόψη μόνο τα μονοπάτια στα οποία η νέα πόλη είναι το τελευταίο σημείο μεταφοράς, και αυτό είναι εύκολο να γίνει, αφού γνωρίζουμε ήδη το ελάχιστο κόστος της διαδρομής προς τη νέα πόλη.
Με άλλα λόγια, κάθε κορυφή από το V συνδέεται με μια ετικέτα - την ελάχιστη γνωστή απόσταση από αυτήν την κορυφή έως το a. Ο αλγόριθμος λειτουργεί βήμα προς βήμα - σε κάθε βήμα «επισκέπτεται» μια κορυφή και προσπαθεί να μειώσει τις ετικέτες. Ο αλγόριθμος τερματίζεται όταν έχουν επισκεφθεί όλες τις κορυφές.
Αρχικοποίηση. Κορυφαία ετικέτα έναυποτίθεται ότι είναι ίσο με 0 , οι ετικέτες των υπόλοιπων κορυφών είναι άπειρες. Αυτό αντανακλά ότι οι αποστάσεις από ένασε άλλες κορυφές είναι ακόμα άγνωστες. Όλες οι κορυφές του γραφήματος επισημαίνονται ως μη επισκέψιμες.
Βήμα αλγόριθμου. Εάν έχουν γίνει επίσκεψη σε όλες τις κορυφές, ο αλγόριθμος τερματίζεται. Διαφορετικά, επιλέγεται μια κορυφή από τις κορυφές που δεν έχουν γίνει ακόμη επίσκεψη uΤο με την ελάχιστη ετικέτα. Εξετάζουμε όλες τις πιθανές διαδρομές στις οποίες uείναι το προτελευταίο σημείο. Κορυφές που συνδέονται με μια κορυφή uακμές, θα ονομάσουμε τους γείτονες αυτής της κορυφής. Για κάθε γείτονα, θεωρήστε ένα νέο μήκος διαδρομής ίσο με το άθροισμα της τρέχουσας ετικέτας uκαι το μήκος της άκρης σύνδεσης uμε αυτόν τον γείτονα. Εάν το μήκος που προκύπτει είναι μικρότερο από την ετικέτα του γείτονα, αντικαταστήστε την ετικέτα με αυτό το μήκος. Έχοντας εξετάσει όλους τους γείτονες, σημειώνουμε την κορυφή uόπως επισκεφθήκατε και επαναλάβετε το βήμα.
Εφόσον ο αλγόριθμος του Dijkstra επιλέγει κάθε φορά να επεξεργάζεται την κορυφή με τη μικρότερη εκτίμηση της συντομότερης διαδρομής, μπορούμε να πούμε ότι ανήκει στους άπληστους αλγόριθμους.
Ας περιγράψουμε με περισσότερες λεπτομέρειες πώς λειτουργεί ο αλγόριθμος του Dijkstra.
Ο αλγόριθμος χρησιμοποιεί τρεις πίνακες αριθμών N (= αριθμός κορυφών δικτύου) ο καθένας. Ο πρώτος πίνακας Α περιέχει ετικέτες με δύο τιμές: 0 (η κορυφή δεν έχει ακόμη ληφθεί υπόψη) και 1 (η κορυφή έχει ήδη θεωρηθεί). ο δεύτερος πίνακας Β περιέχει τις αποστάσεις - τις τρέχουσες μικρότερες αποστάσεις από την αντίστοιχη κορυφή. ο τρίτος πίνακας c περιέχει τους αριθμούς των κορυφών - το k-ο στοιχείο C [k] είναι ο αριθμός της προτελευταίας κορυφής στην τρέχουσα συντομότερη διαδρομή από το Vi στο Vk. Ο πίνακας απόστασης D καθορίζει το μήκος του τόξου D . αν δεν υπάρχει τέτοιο τόξο, τότε στο D εκχωρείται ένας μεγάλος αριθμός Β, ίσος με το «άπειρο της μηχανής».
Τώρα μπορούμε να περιγράψουμε:
1. (αρχικοποίηση). Σε έναν κύκλο από το 1 στο N, γεμίστε τον πίνακα Α με μηδενικά. Συμπληρώστε τον πίνακα C με τον αριθμό i. μετακινήστε την i-η σειρά του πίνακα D στον πίνακα B, A [i]: =1; C [i]: =0 (i - αριθμός κορυφής έναρξης)
2. (γενικό βήμα). Βρείτε το ελάχιστο μεταξύ των μη σημειωμένων (δηλαδή εκείνων k για τα οποία A [k] =0); αφήστε το ελάχιστο να επιτευχθεί στον δείκτη j, δηλ. B[j]<=B [k] Затем выполняются следующие операции: A [j]: =1; если B [k] >B [j] +D , τότε (B [k]: =B [j] +D ; C [k]: =j) (Η συνθήκη σημαίνει ότι η διαδρομή Vi. Vk είναι μεγαλύτερη από τη διαδρομή Vi. Vj Vk) . (Αν σημειωθούν όλα τα A [k], τότε το μήκος της διαδρομής από το Vi στο Vk είναι ίσο με B [k]. Τώρα πρέπει να) απαριθμήσουμε τις κορυφές που περιλαμβάνονται στη συντομότερη διαδρομή).
3. (έκδοση απάντησης). (Η διαδρομή από το Vi στο Vk επιστρέφεται με αντίστροφη σειρά με την ακόλουθη διαδικασία:)
2. Τεύχος ζ;
3. z:=C[z]. Εάν z = 0, τότε τέλος, διαφορετικά πηγαίνετε στο 3.2.
Για να εκτελέσετε τον αλγόριθμο, είναι απαραίτητο να σαρώσετε τον πίνακα Β των N στοιχείων N φορές, δηλ. Ο αλγόριθμος του Dijkstra έχει τετραγωνική πολυπλοκότητα: O(n2).
Παρακάτω είναι ένα μπλοκ διάγραμμα του αλγορίθμου του Dijkstra (βλ. Εικ. 2).
Εικ.2. Διάγραμμα ροής του αλγορίθμου του Dijkstra
Στην αρχή του αλγορίθμου, η απόσταση για την αρχική κορυφή θεωρείται ότι είναι μηδέν και όλες οι άλλες αποστάσεις γεμίζονται με έναν μεγάλο θετικό αριθμό (μεγαλύτερο από τη μέγιστη δυνατή διαδρομή στο γράφημα). Ο πίνακας σημαιών είναι γεμάτος με μηδενικά. Στη συνέχεια ξεκινά ο κύριος βρόχος.
Σε κάθε βήμα του βρόχου, αναζητούμε μια κορυφή με ελάχιστη απόσταση και σημαία ίση με μηδέν. Στη συνέχεια, ορίζουμε τη σημαία σε 1 και ελέγχουμε όλες τις κορυφές που βρίσκονται δίπλα της. Αν η απόσταση σε αυτό είναι μεγαλύτερη από το άθροισμα της απόστασης από την τρέχουσα κορυφή και του μήκους της άκρης, τότε τη μειώνουμε. Ο βρόχος τελειώνει όταν οι σημαίες όλων των κορυφών γίνουν ίσες με 1.
Σε κάθε πόλη της περιοχής (αν μπορείτε να κινηθείτε μόνο κατά μήκος των δρόμων).
Επιλογή 2.Υπάρχουν πολλές πτήσεις μεταξύ των πόλεων του κόσμου, για καθεμία το κόστος είναι γνωστό. Το κόστος μιας πτήσης από το Α στο Β μπορεί να μην είναι ίσο με το κόστος μιας πτήσης από το Β προς το Α. Βρείτε τη διαδρομή ελάχιστου κόστους (πιθανώς με μεταφορά) από την Κοπεγχάγη στο Μπαρναούλ.
Επίσημος ορισμός
Παράδειγμα
Εξετάστε την εκτέλεση του αλγορίθμου στο παράδειγμα του γραφήματος που φαίνεται στο σχήμα.
Ας απαιτείται να βρεθούν οι μικρότερες αποστάσεις από την 1η κορυφή σε όλες τις άλλες.
Υλοποιήσεις σε γλώσσες προγραμματισμού
Εκτέλεση σε γλώσσα C (C).
#define SIZE 6 #define INF 1000000000 int a [ SIZE ][ SIZE ] = (( INF , 5 , INF , INF , INF , INF ),( 1 , 2 , 3 , 4 , 5 // matri ), ( 1 , 2 , 3 , 4 , 5 , 6 ), ( 1 , 2 , 3 , 4 , 5 , 6 ) // οριζόντιοι δείκτες από σημείο { 1 , 2 , 3 , 4 , 5 , 6 },{ 1 , 2 , 3 , 4 , 5 , 6 }}; // κατακόρυφα σε ένα σημείο, τιμή - βάρος int d[ SIZE ]; // πίνακας των συντομότερων διαδρομών που βρέθηκαν, δείκτες - κορυφές γραφήματος void deikstra () ( int v [ SIZE ]; // πίνακας ετικετών int temp , i ; int miniindex , min ; for (i = 0 ; i< SIZE ; i ++ ) { d [ i ] = INF ; // πίνακας μονοπατιών που αρχικοποιήθηκαν στο άπειρο v[i] = 1; ) d [ 0 ] = 0 ; κάνω( // εκτέλεση αλγορίθμου minindex = INF ; min = INF ; για (i = 0; i< SIZE ; i ++ ) { if ((v [ i ] == 1 ) && (d [ i ] < min )) { min = d [ i ]; minindex = i ; } } if (minindex != INF ) { for (i = 0 ; i < SIZE ; i ++ ) { if (a [ minindex ][ i ] >0 ) ( temp = min + a [ miniindex ][ i ]; εάν (θερμ< d [ i ]) d [ i ] = temp ; } } v [ minindex ] = 0 ; } } while (minindex < INF ); }
Δίνεται ένα κατευθυνόμενο ή μη κατευθυνόμενο σταθμισμένο γράφημα με κορυφές και ακμές. Τα βάρη όλων των άκρων είναι μη αρνητικά. Ορίζεται κάποια αρχική κορυφή. Απαιτείται να βρεθούν τα μήκη των συντομότερων μονοπατιών από μια κορυφή σε όλες τις άλλες κορυφές, και επίσης να παρέχει έναν τρόπο για να εξάγονται τα ίδια τα συντομότερα μονοπάτια.
Αυτό το πρόβλημα ονομάζεται πρόβλημα συντομότερων διαδρομών μίας πηγής.
Αλγόριθμος
Αυτό περιγράφει τον αλγόριθμο που προτείνει ο Ολλανδός ερευνητής 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; } } } }Εδώ το γράφημα αποθηκεύεται με τη μορφή λιστών γειτνίασης: για κάθε κορυφή, η λίστα περιέχει μια λίστα ακμών που προέρχονται από αυτήν την κορυφή, δηλ. μια λίστα ζευγών >, όπου το πρώτο στοιχείο του ζεύγους είναι η κορυφή στην οποία οδηγεί η άκρη και το δεύτερο στοιχείο είναι το βάρος της ακμής.
) εκτελείται σε χρόνο O(m + n \ln n) και είναι ο ασυμπτωτικά ταχύτερος γνωστός διαδοχικός αλγόριθμος για αυτήν την κατηγορία προβλημάτων.
1.2 Μαθηματική περιγραφή του αλγορίθμου
Έστω μια γραφική παράσταση G = (V, E) με βάρη ακμής f(e) και κορυφή διακεκριμένης πηγής u . Να συμβολίσετε με d(v) τη μικρότερη απόσταση από την πηγή u έως την κορυφή v .
Ας έχουν ήδη υπολογιστεί όλες οι αποστάσεις που δεν υπερβαίνουν έναν ορισμένο αριθμό r, δηλαδή οι αποστάσεις από τις κορυφές από το σύνολο V_r = \( v \σε V \mid d(v) \le r \). Αφήνω
(v, w) \in \arg\min \(d(v) + f(e) \mid v \in V, e = (v, w) \in E \).Επειτα d(w) = d(v) + f(e), και το v βρίσκεται στο συντομότερο μονοπάτι από το u στο w.
Ποσότητες d^+(w) = d(v) + f(e), όπου v \in V_r , e = (v, w) \in E , καλούνται εκτιμώμενες αποστάσειςκαι είναι άνω φράγμα για πραγματικές αποστάσεις: d(w) \le d^+(w) .
Ο αλγόριθμος του Dijkstra σε κάθε βήμα βρίσκει την κορυφή με τη μικρότερη εκτιμώμενη απόσταση, την επισημαίνει ως επίσκεψη και ενημερώνει τις εκτιμώμενες αποστάσεις για όλα τα τελικά σημεία των ακμών που προέρχονται από αυτήν.
1.3 Υπολογιστικός πυρήνας του αλγορίθμου
Οι κύριοι υπολογισμοί σχετίζονται με πράξεις στην ουρά προτεραιότητας:
- εξαγωγή του ελάχιστου στοιχείου (delete_min).
- μειώστε την προτεραιότητα ενός στοιχείου (decrease_key).
1.4 Μακροδομή του αλγορίθμου
Αλγόριθμος ψευδοκώδικας:
Εισαγωγή δεδομένων: γράφημα με κορυφές V, άκρα μιμε ζυγαριά φά(μι) κόμβος πηγής u. Παραγωγή: αποστάσεις ρε(v) σε κάθε κορυφή v ∈ VΑπο πάνω u. Q := νέοςουρά προτεραιότητας για κάθε v ∈ V: αν v = u έπειτα ρε(v) := 0 αλλού ρε(v) := ∞ Q.εισάγετε( v, ρε(v)) ενώ Q ≠ ∅: v := Q.delete_min() για κάθε μι = (v, w) ∈ μι: αν ρε(w) > ρε(v) + φά(μι): ρε(w) := ρε(v) + φά(μι) Q.decrease_key( w, ρε(w))1.5 Σχέδιο υλοποίησης διαδοχικών αλγορίθμων
Η συγκεκριμένη υλοποίηση του αλγορίθμου του Dijkstra καθορίζεται από την επιλογή του αλγορίθμου ουράς προτεραιότητας που χρησιμοποιείται. Στην απλούστερη περίπτωση, αυτό μπορεί να είναι ένας πίνακας ή μια λίστα, η αναζήτηση ενός ελάχιστου στο οποίο απαιτεί την προβολή όλων των κορυφών. Πιο αποτελεσματικό είναι να χρησιμοποιήσετε το σωρό. η πιο γνωστή εκτίμηση πολυπλοκότητας είναι για την παραλλαγή που χρησιμοποιεί το σωρό Fibonacci.
Μια επιλογή υλοποίησης είναι δυνατή όταν προστίθενται κορυφές στην ουρά όχι στο στάδιο της προετοιμασίας, αλλά κατά τη στιγμή της πρώτης επίσκεψης.
1.6 Διαδοχική πολυπλοκότητα του αλγορίθμου
Η διαδοχική πολυπλοκότητα του αλγορίθμου είναι O(C_1 m + C_2n) , όπου
- C_1 – ο αριθμός των λειτουργιών για τη μείωση της απόστασης στην κορυφή.
- C_2 είναι ο αριθμός των πράξεων για τον υπολογισμό του ελάχιστου.
Ο αρχικός αλγόριθμος του Dijkstra χρησιμοποιούσε λίστες ως εσωτερική δομή δεδομένων, για τις οποίες C_1 = O(1) , C_2 = O(n) , επομένως η συνολική πολυπλοκότητα ήταν O(n^2) .
Όταν χρησιμοποιείται ο σωρός Fibonacci, ο ελάχιστος χρόνος υπολογισμού μειώνεται σε C_2 = O(\ln n) , επομένως η συνολική πολυπλοκότητα είναι O(m + n \ln n) , που είναι το ασυμπτωτικά πιο γνωστό αποτέλεσμα για αυτήν την κατηγορία προβλημάτων.
1.7 Γράφημα πληροφοριών
Δίνεται ένα γράφημα αλγορίθμου για τη βασική υλοποίηση του αλγορίθμου του Dijkstra σε λίστες ή πίνακες.
Εικόνα 1. Γράφημα αλγορίθμου χωρίς εμφάνιση δεδομένων εισόδου και εξόδου. n=3. Οι πράξεις σύγκρισης σημειώνονται με κίτρινο χρώμα, οι πράξεις αλλαγής ετικετών κορυφών σημειώνονται με πράσινο και η επισήμανση κορυφής σημειώνεται με μπλε.
1.8 Πηγή παραλληλισμού αλγορίθμων
Ο αλγόριθμος του Dijkstra επιτρέπει αποτελεσματική παραλληλοποίηση, μέσο χρόνο λειτουργίας O(n^(1/3)\ln n) με όγκο υπολογισμού O(n \ln n + m) .
Η πρώτη εκτίμηση βασίζεται στο χαρακτηριστικό daps, το οποίο μετρά τον αριθμό των προσβάσεων στη μνήμη (ανάγνωση και εγγραφή) που πραγματοποιούνται ανά δευτερόλεπτο. Αυτό το χαρακτηριστικό είναι ανάλογο με την εκτίμηση των flops σε σχέση με την εργασία με τη μνήμη και είναι περισσότερο μια εκτίμηση της απόδοσης της αλληλεπίδρασης με τη μνήμη παρά μια εκτίμηση της τοποθεσίας. Ωστόσο, χρησιμεύει ως καλή πηγή πληροφοριών, μεταξύ άλλων για σύγκριση με τα αποτελέσματα για την ακόλουθη δυνατότητα cvg.
Το σχήμα 6 δείχνει τις τιμές daps για υλοποιήσεις κοινών αλγορίθμων, ταξινομημένες με αύξουσα σειρά (όσο περισσότερα daps, τόσο καλύτερη είναι η απόδοση γενικά). Μπορείτε να δείτε ότι η απόδοση της μνήμης είναι αρκετά χαμηλή. Αυτό δεν προκαλεί έκπληξη, καθώς οι υλοποιήσεις αλγορίθμων πάνω από γραφήματα έχουν σχεδόν πάντα χαμηλή απόδοση λόγω της ανωμαλίας πρόσβασης στα δεδομένα, την οποία είδαμε κατά την ανάλυση του προφίλ πρόσβασης.
Εικόνα 6. Σύγκριση τιμών βαθμολογίας daps
Το δεύτερο χαρακτηριστικό, cvg, προορίζεται να παρέχει μια πιο ανεξάρτητη από τη μηχανή εκτίμηση τοποθεσίας. Καθορίζει πόσο συχνά χρειάζεται το πρόγραμμα να τραβάει δεδομένα στην κρυφή μνήμη. Κατά συνέπεια, όσο μικρότερη είναι η τιμή cvg, τόσο λιγότερο συχνά χρειάζεται να γίνεται, τόσο καλύτερη είναι η τοποθεσία.
Το σχήμα 7 δείχνει τις τιμές cvg για το ίδιο σύνολο υλοποιήσεων, ταξινομημένες με φθίνουσα σειρά (όσο μικρότερο είναι το cvg, τόσο υψηλότερη είναι η τοποθεσία γενικά). Μπορεί να φανεί ότι σε αυτή την περίπτωση, η τιμή cvg συσχετίζεται καλά με τη βαθμολογία απόδοσης και αντικατοπτρίζει χαμηλή εντοπιότητα, η οποία είναι σύμφωνη με τα ευρήματα της ποιοτικής αξιολόγησης τοπικότητας.
Εικόνα 7. Σύγκριση τιμών βαθμολογίας cvg
2.3 Πιθανές μέθοδοι και χαρακτηριστικά της παράλληλης υλοποίησης του αλγορίθμου
2.4 Επεκτασιμότητα του αλγορίθμου και εφαρμογή του
2.4.1 Επεκτασιμότητα του αλγορίθμου
2.4.2 Επεκτασιμότητα της υλοποίησης του αλγορίθμου
Ας μελετήσουμε την επεκτασιμότητα της παράλληλης υλοποίησης του αλγορίθμου σύμφωνα με τη μεθοδολογία. Η μελέτη διεξήχθη στον υπερυπολογιστή Lomonosov του συγκροτήματος υπερυπολογιστών του Πανεπιστημίου της Μόσχας. Το σύνολο και τα όρια των τιμών των μεταβλητών παραμέτρων για την εκκίνηση της υλοποίησης του αλγορίθμου:
- αριθμός επεξεργαστών με ακέραιες τετράγωνες τιμές.
- Μέγεθος γραφήματος με βήμα 16000.
Το παρακάτω σχήμα δείχνει ένα γράφημα της απόδοσης της επιλεγμένης υλοποίησης του αλγορίθμου ανάλογα με τις μεταβλητές παραμέτρους εκκίνησης.
Εικόνα 8. Παράλληλη υλοποίηση του αλγορίθμου. Αλλαγή στην απόδοση ανάλογα με τον αριθμό των επεξεργαστών και το μέγεθος της περιοχής.
Λόγω των ιδιαιτεροτήτων της παράλληλης υλοποίησης του αλγορίθμου, η συνολική απόδοση είναι αρκετά χαμηλή και αυξάνεται αργά με την αύξηση του αριθμού των διεργασιών και όταν πλησιάζει ο αριθμός των διεργασιών 128, αρχίζει να μειώνεται. Αυτό εξηγείται από τη χρήση συλλογικών λειτουργιών σε κάθε επανάληψη του αλγορίθμου και από το γεγονός ότι το κόστος των ανταλλαγών επικοινωνίας αυξάνεται σημαντικά με την αύξηση του αριθμού των διαδικασιών που χρησιμοποιούνται. Οι υπολογισμοί για κάθε διεργασία είναι αρκετά γρήγοροι και επομένως η αποσύνθεση του γραφήματος αντισταθμίζει ασθενώς την επίδραση του κόστους των ανταλλαγών επικοινωνίας.
2.5 Δυναμική απόδοση και αποτελεσματικότητα υλοποίησης αλγορίθμων
Για τα πειράματα χρησιμοποιήθηκε η υλοποίηση του αλγορίθμου του Dijkstra. Όλα τα αποτελέσματα ελήφθησαν στον υπερυπολογιστή Lomonosov. Χρησιμοποιήσαμε επεξεργαστές Intel Xeon X5570 με κορυφαία απόδοση 94 Gflops, καθώς και μεταγλωττιστή intel 13.1.0. Τα σχήματα δείχνουν την αποτελεσματικότητα της εφαρμογής του αλγόριθμου του Dijkstra σε 32 διεργασίες.
Εικόνα 9. Γράφημα φόρτωσης CPU κατά την εκτέλεση του αλγόριθμου του Dijkstra
Το γράφημα φόρτωσης του επεξεργαστή δείχνει ότι σχεδόν σε όλη τη διάρκεια της εκτέλεσης του προγράμματος, το επίπεδο φόρτωσης είναι περίπου 50%. Αυτό υποδηλώνει ομοιόμορφο φορτίο στους επεξεργαστές, όταν χρησιμοποιούνται 8 διεργασίες ανά κόμβο υπολογισμού και χωρίς χρήση Hyper Threading.
Σχήμα 10. Διάγραμμα πράξεων κινητής υποδιαστολής ανά δευτερόλεπτο κατά την εκτέλεση του αλγόριθμου του Dijkstra
Το σχήμα 10 δείχνει ένα γράφημα πράξεων κινητής υποδιαστολής ανά δευτερόλεπτο. Το γράφημα δείχνει μια συνολική πολύ κακή απόδοση περίπου 250 Kflops στην κορυφή και περίπου 150 Kflops κατά μέσο όρο σε όλους τους κόμβους. Αυτό δείχνει ότι σχεδόν όλοι οι υπολογισμοί στο πρόγραμμα γίνονται με ακέραιους αριθμούς.
Το γράφημα εγγραφής στη μνήμη δείχνει ένα παρόμοιο μοτίβο υπολογιστικής ανομοιομορφίας, με λίγες μόνο διεργασίες να γράφουν ενεργά ταυτόχρονα. Αυτό συσχετίζεται με άλλα χρονοδιαγράμματα εκτέλεσης. Αξίζει να σημειωθεί ο σχετικά χαμηλός αριθμός προσπελάσεων εγγραφής στη μνήμη. Αυτό υποδηλώνει καλή οργάνωση των υπολογισμών και αρκετά αποτελεσματική εργασία με τη μνήμη.
Εικόνα 15. Γράφημα του ρυθμού μεταφοράς μέσω του δικτύου Infiniband σε byte / sec όταν εκτελείται ο αλγόριθμος του Dijkstra
Στο γράφημα ρυθμού μεταφοράς δεδομένων δικτύου Infiniband, υπάρχει ένας αρκετά υψηλός ρυθμός μεταφοράς δεδομένων σε byte ανά δευτερόλεπτο. Αυτό υποδηλώνει ότι οι διεργασίες ανταλλάσσουν εντατικά και πιθανώς αρκετά μικρά τμήματα δεδομένων μεταξύ τους, επειδή η υπολογιστική απόδοση είναι υψηλή. Αξίζει να σημειωθεί ότι ο ρυθμός μεταφοράς διαφέρει μεταξύ των διεργασιών, υποδεικνύοντας μια υπολογιστική ανισορροπία.
Εικόνα 16. Γράφημα του ρυθμού μεταφοράς μέσω του δικτύου Infiniband σε πακέτα / δευτερόλεπτο όταν εκτελείται ο αλγόριθμος του Dijkstra
Στο γράφημα του ρυθμού μεταφοράς δεδομένων σε πακέτα ανά δευτερόλεπτο, υπάρχει εξαιρετικά υψηλή ένταση μεταφοράς δεδομένων. Αυτό υποδηλώνει ότι, πιθανώς, οι διαδικασίες ανταλλάσσουν όχι πολύ σημαντικές ποσότητες δεδομένων, αλλά πολύ εντατικά. Οι συλλογικές λειτουργίες χρησιμοποιούνται σε κάθε βήμα με μικρά τμήματα δεδομένων, γεγονός που εξηγεί αυτήν την εικόνα. Υπάρχει επίσης λιγότερη ανισορροπία μεταξύ των διεργασιών από ό,τι φαίνεται στα γραφήματα χρήσης μνήμης, υπολογισμού και μεταφοράς δεδομένων byte/sec. Αυτό δείχνει ότι οι διεργασίες ανταλλάσσουν τον ίδιο αριθμό πακέτων σύμφωνα με τον αλγόριθμο, αλλά λαμβάνουν διαφορετικές ποσότητες δεδομένων και εκτελούν ανομοιόμορφους υπολογισμούς.
Εικόνα 17. Γράφημα του αριθμού των διεργασιών που περιμένουν να εισέλθουν στο στάδιο μέτρησης (Loadavg) όταν εκτελείται ο αλγόριθμος του Dijkstra
Το γράφημα του αριθμού των διεργασιών που περιμένουν να εισέλθουν στο στάδιο μέτρησης (Loadavg) δείχνει ότι η τιμή αυτής της παραμέτρου είναι σταθερή σε όλη τη λειτουργία του προγράμματος και είναι περίπου ίση με 8. Αυτό δείχνει τη σταθερή λειτουργία του προγράμματος με φορτωμένους υπολογισμούς από όλους κόμβους. Αυτό υποδηλώνει μια πολύ ορθολογική και στατική φόρτωση πόρων υλικού από διεργασίες. Και δείχνει μια αρκετά καλή αποτελεσματικότητα της υλοποίησης που εκτελείται. Σε γενικές γραμμές, σύμφωνα με την παρακολούθηση συστήματος του προγράμματος, μπορεί να συναχθεί το συμπέρασμα ότι το πρόγραμμα λειτούργησε αρκετά αποτελεσματικά και σταθερά. Η χρήση μνήμης είναι πολύ εντατική και η χρήση μέσων επικοινωνίας είναι εξαιρετικά εντατική, ενώ οι όγκοι μεταφοράς δεδομένων δεν είναι υψηλοί. Αυτό υποδεικνύει την ακριβή φύση του λανθάνοντος χρόνου του περιβάλλοντος επικοινωνίας του αλγοριθμικού μέρους του προγράμματος. Η χαμηλή απόδοση φαίνεται να συνδέεται με έναν μάλλον υψηλό όγκο μεταφορών σε κάθε διαδικασία και με εντατικές ανταλλαγές μηνυμάτων.