ΕΛΑΧΙΣΤΕΣ ΔΙΑΔΡΟΜΕΣ ΚΑΙ ΚΥΚΛΩΜΑΤΑ

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

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

Στα πλαίσια του αλγόριθμου αυτού w(u_i ,u_j) δηλώνει το βάρος της ακμής μεταξύ των κορυφών u_i και u_{j .}Αν υπάρχουν περισσότερες από μία ακμές τότε w(u_i ,u_j) δηλώνει το μικρότερο βάρος από τα βάρη που αντιστοιχούν σε όλες αυτές τις ακμές.Τα βάρη βρόγχων παραλείπονται.Επίσης θα συμβολίσουμε με min [α,β] τον μικρότερο από τους α,β.

Αλγόριθμο του Dijkstra

Ζητείται να βρεθούν οι διαδρομές ελαχίστου βάρους από την κορυφή r στην κορυφή s ενός σταθμισμένου ψευδογραφήματος G.

0. Για κάθε ζεύγος προσκείμενων κορυφών υ και u του G ψευδογραφήματος w(υ,u) είναι το ελάχιστο βάρος μιας ακμής που ενώνει τις κορυφές υ και u.

1. L(r)← 0 για όλες τις άλλες κορυφές u ≠ r , L(u)←∞

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

3.Για κάθε προσκείμενη κορυφή u της υ υπολογίστε τα L(υ) ←min[L(υ),L(υ)+ w(u ,υ)].

4.Αν s δεν έχει σημειωθεί με κύκλο πήγαινε στο 2.

Σε άλλη περίπτωση STOP.