Ο αλγόριθμος συντομότερης διαδρομής της Dijkstra - Μια λεπτομερής και οπτική εισαγωγή

Καλως ΗΡΘΑΤΕ! Αν θέλετε πάντα να μάθετε και να κατανοήσετε τον αλγόριθμο της Dijkstra, τότε αυτό το άρθρο είναι για εσάς. Θα δείτε πώς λειτουργεί πίσω από τα παρασκήνια με μια βήμα προς βήμα γραφική εξήγηση.

Θα μάθεις:

  • Βασικές έννοιες γραφημάτων (μια γρήγορη ανασκόπηση).
  • Σε ποιον λόγο χρησιμοποιείται ο Αλγόριθμος της Dijkstra.
  • Πώς λειτουργεί πίσω από τα παρασκήνια με ένα βήμα προς βήμα παράδειγμα.

Ας ξεκινήσουμε. ✨

? Εισαγωγή στα γραφήματα

Ας ξεκινήσουμε με μια σύντομη εισαγωγή στα γραφήματα.

ΒΑΣΙΚΕΣ ΕΝΝΟΙΕΣ

Τα γραφήματα είναι δομές δεδομένων που χρησιμοποιούνται για την αναπαράσταση "συνδέσεων" μεταξύ ζευγών στοιχείων.

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

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

Οι κόμβοι αντιπροσωπεύονται με χρωματιστούς κύκλους και τα άκρα αντιπροσωπεύονται με γραμμές που συνδέουν αυτούς τους κύκλους.

? Συμβουλή: Δύο κόμβοι συνδέονται εάν υπάρχει ένα άκρο μεταξύ τους.

Εφαρμογές

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

Τύποι γραφημάτων

Τα γραφήματα μπορούν να είναι:

  • Άμεσο: εάν για κάθε ζεύγος συνδεδεμένων κόμβων, μπορείτε να μεταβείτε από τον ένα κόμβο στον άλλο και στις δύο κατευθύνσεις.
  • Σκηνοθεσία: εάν για κάθε ζεύγος συνδεδεμένων κόμβων, μπορείτε να μεταβείτε μόνο από έναν κόμβο στον άλλο σε μια συγκεκριμένη κατεύθυνση. Χρησιμοποιούμε βέλη αντί για απλές γραμμές για να αντιπροσωπεύουμε κατευθυνόμενες άκρες.

? Συμβουλή: σε αυτό το άρθρο, θα δουλέψουμε με μη κατευθυνόμενα γραφήματα.

Σταθμισμένα γραφήματα

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

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

? Συμβουλή: Αυτά τα βάρη είναι απαραίτητα για τον Αλγόριθμο της Dijkstra. Θα δείτε γιατί σε λίγο.

? Εισαγωγή στον Αλγόριθμο της Dijkstra

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

  • Σκοπός και περιπτώσεις χρήσης
  • Ιστορία
  • Βασικά στοιχεία του αλγορίθμου
  • Απαιτήσεις

Σκοπός και περιπτώσεις χρήσης

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

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

Ιστορία

Αυτός ο αλγόριθμος δημιουργήθηκε και δημοσιεύθηκε από τον Δρ Edsger W. Dijkstra, έναν λαμπρό Ολλανδό επιστήμονα υπολογιστών και μηχανικό λογισμικού.

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

Κατά τη διάρκεια συνέντευξής του το 2001, ο Δρ Dijkstra αποκάλυψε πώς και γιατί σχεδίασε τον αλγόριθμο:

Ποιος είναι ο πιο σύντομος τρόπος για να ταξιδέψετε από Ρότερνταμ προς Γκρόνινγκεν; Είναι ο αλγόριθμος για τη συντομότερη διαδρομή, τον οποίο σχεδίασα σε περίπου 20 λεπτά. Ένα πρωί έκανα ψώνια στο Άμστερνταμ με τη νεαρή αρραβωνιαστικιά μου και κουρασμένοι, καθίσαμε στη βεράντα του καφέ για να πιούμε ένα φλιτζάνι καφέ και απλά σκεφτόμουν αν θα μπορούσα να το κάνω αυτό, και στη συνέχεια σχεδίασα τον αλγόριθμο για το συντομότερο μονοπάτι . Όπως είπα, ήταν μια εφεύρεση 20 λεπτών. Στην πραγματικότητα, δημοσιεύθηκε το 1959, τρία χρόνια αργότερα. Η έκδοση είναι ακόμα αρκετά ωραία. Ένας από τους λόγους που είναι τόσο ωραίο ήταν ότι το σχεδίασα χωρίς μολύβι και χαρτί. Χωρίς μολύβι και χαρτί, είστε σχεδόν αναγκασμένοι να αποφύγετε όλες τις περιπλοκές που μπορούν να αποφευχθούν. Τελικά αυτός ο αλγόριθμος έγινε, με μεγάλη έκπληξη, ένας από τους ακρογωνιαίους λίθους της φήμης μου. - Όπως αναφέρεται στο άρθρο Edsger W.Dijkstra από μια συνέντευξη με τον Edsger W. Dijkstra.

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

Βασικά στοιχεία του Αλγόριθμου της Dijkstra

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

Απαιτήσεις

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

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

? Παράδειγμα του Αλγόριθμου της Dijkstra

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

Έχουμε αυτό το γράφημα:

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

? Συμβουλή: Για αυτό το γράφημα, θα υποθέσουμε ότι το βάρος των άκρων αντιπροσωπεύει την απόσταση μεταξύ δύο κόμβων.

Θα έχουμε τη συντομότερη διαδρομή από κόμβο 0σε κόμβο 1, από κόμβο 0σε κόμβο 2, από κόμβο 0σε κόμβο 3, και ούτω καθεξής για κάθε κόμβο στο γράφημα.

Αρχικά, έχουμε αυτήν τη λίστα αποστάσεων (δείτε την παρακάτω λίστα):

  • Η απόσταση από τον κόμβο προέλευσης από τον εαυτό του είναι 0. Για αυτό το παράδειγμα, ο κόμβος προέλευσης θα είναι κόμβος, 0αλλά μπορεί να είναι οποιοσδήποτε κόμβος που επιλέγετε.
  • Η απόσταση από τον κόμβο προέλευσης προς όλους τους άλλους κόμβους δεν έχει καθοριστεί ακόμη, επομένως χρησιμοποιούμε το σύμβολο απείρου για να το αντιπροσωπεύσουμε αρχικά.

Έχουμε επίσης αυτήν τη λίστα (δείτε παρακάτω) για να παρακολουθείτε τους κόμβους που δεν έχουν επισκεφτεί ακόμα (κόμβοι που δεν έχουν συμπεριληφθεί στη διαδρομή):

? Συμβουλή: Θυμηθείτε ότι ο αλγόριθμος ολοκληρώνεται όταν όλοι οι κόμβοι έχουν προστεθεί στη διαδρομή.

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

Τώρα πρέπει να αρχίσουμε να ελέγχουμε την απόσταση από τον κόμβο 0στους γειτονικούς κόμβους του. Όπως μπορείτε να δείτε, αυτοί είναι κόμβοι 1και 2(δείτε τις κόκκινες άκρες):

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

Πρέπει να ενημερώσουμε τις αποστάσεις από κόμβο 0σε κόμβο 1και κόμβο 2με τα βάρη των άκρων που τις συνδέουν στον κόμβο 0(ο κόμβος προέλευσης). Αυτά τα βάρη είναι 2 και 6, αντίστοιχα:

Μετά την ενημέρωση των αποστάσεων των παρακείμενων κόμβων, πρέπει:

  • Επιλέξτε τον κόμβο που βρίσκεται πιο κοντά στον κόμβο προέλευσης με βάση τις τρέχουσες γνωστές αποστάσεις.
  • Επισήμανση ως επισκέφθηκε.
  • Προσθέστε το στο μονοπάτι.

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

Στο διάγραμμα, μπορούμε να το αντιπροσωπεύσουμε με ένα κόκκινο άκρο:

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

Το διαγράφουμε από τη λίστα των μη επισκεπτόμενων κόμβων:

Τώρα πρέπει να αναλύσουμε τους νέους γειτονικούς κόμβους για να βρούμε τη συντομότερη διαδρομή για να τους φτάσουμε. Θα αναλύσουμε μόνο τους κόμβους που βρίσκονται δίπλα στους κόμβους που είναι ήδη μέρος της συντομότερης διαδρομής (η διαδρομή που επισημαίνεται με κόκκινες άκρες).

Ο κόμβος 3και ο κόμβος 2είναι και οι δύο δίπλα σε κόμβους που βρίσκονται ήδη στη διαδρομή επειδή συνδέονται άμεσα με κόμβο 0και κόμβο 1, αντίστοιχα, όπως μπορείτε να δείτε παρακάτω. Αυτοί είναι οι κόμβοι που θα αναλύσουμε στο επόμενο βήμα.

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

Αυτή η απόσταση είναι 7 . Ας δούμε γιατί.

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

  • Για κόμβο 3: η συνολική απόσταση είναι 7 επειδή προσθέτουμε τα βάρη των άκρων που σχηματίζουν τη διαδρομή 0 -> 1 -> 3(2 για την άκρη 0 -> 1και 5 για την άκρη 1 -> 3).

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

Από τη λίστα των αποστάσεων, μπορούμε αμέσως να εντοπίσουμε ότι αυτός είναι κόμβος 2με την απόσταση 6 :

Το προσθέτουμε στη διαδρομή γραφικά με ένα κόκκινο περίγραμμα γύρω από τον κόμβο και ένα κόκκινο άκρο:

Το επισημαίνουμε επίσης ως επισκέψιμο, προσθέτοντας ένα μικρό κόκκινο τετράγωνο στη λίστα αποστάσεων και διασχίζοντας το από τη λίστα των μη επισκεπτόμενων κόμβων:

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

Μπορείτε να δείτε ότι έχουμε δύο πιθανές διαδρομές 0 -> 1 -> 3ή 0 -> 2 -> 3. Ας δούμε πώς μπορούμε να αποφασίσουμε ποια είναι η πιο σύντομη διαδρομή.

Ο κόμβος 3έχει ήδη μια απόσταση στη λίστα που καταγράφηκε προηγουμένως ( 7, δείτε την παρακάτω λίστα). Αυτή η απόσταση ήταν το αποτέλεσμα ενός προηγούμενου βήματος, όπου προσθέσαμε τα βάρη 5 και 2 από τα δύο άκρα που χρειαζόμασταν για να διασχίσουμε το μονοπάτι 0 -> 1 -> 3.

Αλλά τώρα έχουμε μια άλλη εναλλακτική λύση. Εάν επιλέξουμε να ακολουθήσουμε το μονοπάτι 0 -> 2 -> 3, θα πρέπει να ακολουθήσουμε δύο άκρες 0 -> 2και 2 -> 3με βάρη 6 και 8 ,αντίστοιχα,που αντιπροσωπεύει μια συνολική απόσταση 14 .

Είναι σαφές ότι η πρώτη (υπάρχουσα) απόσταση είναι μικρότερη (7 έναντι 14), οπότε θα επιλέξουμε να διατηρήσουμε την αρχική διαδρομή 0 -> 1 -> 3. Ενημερώνουμε την απόσταση μόνο εάν η νέα διαδρομή είναι μικρότερη.

Ως εκ τούτου, θα προσθέσετε αυτό το κόμβο στη διαδρομή χρησιμοποιώντας την πρώτη εναλλακτική λύση: 0 -> 1 -> 3.

Σημειώνουμε αυτόν τον κόμβο ως επισκέψιμο και τον διαγράφουμε από τη λίστα των μη επισκέψιμων κόμβων:

Τώρα επαναλαμβάνουμε τη διαδικασία ξανά.

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

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

  • Για κόμβο 4: η απόσταση είναι 17 από τη διαδρομή   0 -> 1 -> 3 -> 4.
  • Για κόμβο 5: η απόσταση είναι 22 από τη διαδρομή 0 -> 1 -> 3 -> 5.

? Συμβουλή: Παρατηρήστε ότι μπορούμε να εξετάσουμε το ενδεχόμενο επέκτασης της μικρότερης διαδρομής (επισημαίνεται με κόκκινο χρώμα). Δεν μπορούμε να εξετάσουμε μονοπάτια που θα μας οδηγήσουν σε άκρες που δεν έχουν προστεθεί στη συντομότερη διαδρομή (για παράδειγμα, δεν μπορούμε να σχηματίσουμε μια διαδρομή που περνά από την άκρη 2 -> 3).

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

Το επισημαίνουμε επίσης ως "επισκέφθηκε" προσθέτοντας ένα μικρό κόκκινο τετράγωνο στη λίστα:

Και το διαγράφουμε από τη λίστα των μη επισκεπτόμενων κόμβων:

Και επαναλαμβάνουμε τη διαδικασία ξανά. Ελέγχουμε τις γειτονικές κόμβους: κόμβου 5και του κόμβου 6. Πρέπει να αναλύσουμε κάθε πιθανή διαδρομή που μπορούμε να ακολουθήσουμε για να φτάσουμε σε αυτούς από κόμβους που έχουν ήδη επισημανθεί ως επισκέψεις και προστέθηκαν στη διαδρομή.

Για κόμβο 5:

  • Η πρώτη επιλογή είναι να ακολουθήσετε τη διαδρομή 0 -> 1 -> 3 -> 5, η οποία έχει απόσταση 22 από τον κόμβο προέλευσης (2 + 5 + 15). Αυτή η απόσταση είχε ήδη καταγραφεί στη λίστα αποστάσεων σε ένα προηγούμενο βήμα.
  • Η δεύτερη επιλογή θα ήταν να ακολουθήσετε τη διαδρομή 0 -> 1 -> 3 -> 4 -> 5, η οποία έχει απόσταση 23 από τον κόμβο προέλευσης (2 + 5 + 10 + 6).

Είναι σαφές ότι η πρώτη διαδρομή είναι μικρότερη, οπότε την επιλέγουμε για κόμβο 5.

Για κόμβο 6:

  • Η διαθέσιμη διαδρομή είναι 0 -> 1 -> 3 -> 4 -> 6, η οποία έχει απόσταση 19 από τον κόμβο προέλευσης (2 + 5 + 10 + 2).

Σημειώνουμε τον κόμβο με τη μικρότερη (επί του παρόντος γνωστή) απόσταση κατά την επίσκεψη. Σε αυτήν την περίπτωση, κόμβος 6.

Και το διαγράφουμε από τη λίστα των μη επισκεπτόμενων κόμβων:

Τώρα έχουμε αυτό το μονοπάτι (επισημαίνεται με κόκκινο χρώμα):

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

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

  • Επιλογή 1:0 -> 1 -> 3 -> 5 με απόσταση 22 (2 + 5 + 15).
  • Επιλογή 2:0 -> 1 -> 3 -> 4 -> 5 με απόσταση 23 (2 + 5 + 10 + 6).
  • Επιλογή 3:0 -> 1 -> 3 -> 4 -> 6 -> 5 με απόσταση 25 (2 + 5 + 10 + 2 + 6).

Επιλέγουμε τη συντομότερη διαδρομή: 0 -> 1 -> 3 -> 5με απόσταση 22 .

Σημειώνουμε τον κόμβο ως επισκέψιμο και τον διαγράφουμε από τη λίστα των μη επισκέψιμων κόμβων:

Και voilà! Έχουμε το τελικό αποτέλεσμα με τη συντομότερη διαδρομή από κόμβο 0σε κάθε κόμβο στο γράφημα.

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

Για παράδειγμα, εάν θέλετε να φτάσετε σε έναν κόμβο 6ξεκινώντας από έναν κόμβο 0, απλά πρέπει να ακολουθήσετε τις κόκκινες άκρες και θα ακολουθείτε 0 -> 1 -> 3 -> 4 - > 6αυτόματα τη συντομότερη διαδρομή .

? Συνοπτικά

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

Ελπίζω πραγματικά ότι σας άρεσε το άρθρο μου και το βρήκα χρήσιμο. Τώρα ξέρετε πώς λειτουργεί ο Αλγόριθμος της Dijkstra πίσω από τα παρασκήνια. Ακολουθήστε με στο Twitter @EstefaniaCassN και δείτε τα διαδικτυακά μου μαθήματα.