ΠΛΗ20 Μάθημα 5.4 – Ο αλγόριθμος του Dijkstra


Στόχοι του Μαθήματος

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

Σύντομη Παρουσίαση

Με μια ματιά το μάθημα:

  • ΚΑΡΤΑ: Ο αλγόριθμος του Dijkstra


Σχολιασμός (βίντεο)

Αναλυτική Παρουσίαση

ΠΕΡΙΕΧΟΜΕΝΑ ΜΑΘΗΜΑΤΟΣ:

1) Συντομότερα Μονοπάτια
1.1) Γράφημα με Βάρη
1.2) Συντομότερο Μονοπάτι
2) Ο αλγόριθμος του Dijkstra
2.1) Διατύπωση του Προβλήματος
2.2) Ψευδογλώσσα του Αλγορίθμου
2.3) Παράδειγμα Εκτέλεσης
3) Παρατηρήσεις στον αλγόριθμο του Dijkstra
3.1) Δένδρο Συντομότερων Μονοπατιών
3.2) Αρνητικά Βάρη
3.3) Ιδιότητες Συντομότερων Μονοπατιών
Ασκήσεις

Παρουσίαση τουΜαθήματος:


ΒΙΝΤΕΟ ΜΑΘΗΜΑΤΟΣ και ΣΧΟΛΙΑΣΜΟΣ

ΣΥΜΒΟΥΛΕΣ

 riddler.200  batman.200
ΚατηγορίαΧΔΣχόλιο
ΘεωρίαΠαρουσίαση Αλγορίθμου με ένα αντιπροσωπευτικό παράδειγμα. Ιδιότητες Βέλτιστων Μονοπατιών
Κατανόηση 151Εφαρμογή του αλγορίθμου σε ένα μη κατευθυνόμενο γράφημα
Κατανόηση 251Εφαρμογή του αλγορίθμου σε ένα κατευθυνόμενο γράφημα
Κατανόηση 353Εφαρμογή του αλγορίθμου σε ένα μη κατευθυνόμενο γράφημα
Ερωτήσεις 152Ερωτήσεις κατανόησης σε ένα κατευθυνόμενο γράφημα
Ερωτήσεις 252Ερωτήσεις κατανόησης σε ένα κατευθυνόμενο γράφημα
Ερωτήσεις 352Ερωτήσεις κατανόησης σε ένα κατευθυνόμενο γράφημα
Εφαρμογή 143"Το συντομότερο μονοπάτι δεν αλλάζει αν πολλαπλασιάσουμε τα βάρη με τον ίδιο θετικό αριθμό"
Εφαρμογή 243"Το συντομότερο μονοπάτι δεν αλλάζει αν προσθέσουμε στα βάρη τον ίδιο θετικό αριθμό"
Εφαρμογή 353"Κάθε υπομονοπάτι ενός βέλτιστου μονοπατιού είναι βέλτιστο"

Περαιτέρω Εξάσκηση

(-)

Πηγές και Διαδίκτυο

Οι λυμένες ασκήσεις και οι ερωτήσεις είναι θέματα εξετάσεων-εργασιών του ΕΑΠ

Εκτυπώσιμη μορφή αρχείων PDF