Dijkstra — μη αρνητικά βάρη και ουρά προτεραιότητας

Python 3 reference program

import heapq
def distances(graph, start):
    dist = {start: 0}; heap = [(0, start)]
    while heap:
        cost, node = heapq.heappop(heap)
        if cost != dist[node]: continue
        for neighbor, weight in graph.get(node, []):
            if weight < 0: raise ValueError('negative weight')
            candidate = cost + weight
            if candidate < dist.get(neighbor, float('inf')):
                dist[neighbor] = candidate
                heapq.heappush(heap, (candidate, neighbor))
    return dist
assert distances({'a':[('b',3),('c',1)],'c':[('b',1)]},'a')['b'] == 2

Μηχανισμός

Ο γράφος αντιστοιχίζει κάθε κόμβο σε ακμές (neighbor, weight). Η heap ανασύρει τη μικρότερη προσωρινή απόσταση. Αν το ζεύγος που βγαίνει δεν συμφωνεί με dist[node], είναι παλιά εγγραφή και αγνοείται. Η ορθότητα της μεθόδου στηρίζεται σε μη αρνητικά βάρη των ακμών.

Ερμηνεία εξόδου

Για a→b=3, a→c=1 και c→b=1, η ελάχιστη απόσταση έως b είναι 2 μέσω c. Η συνάρτηση επιστρέφει αποστάσεις, όχι τις ίδιες τις διαδρομές. Μη προσβάσιμοι κόμβοι απουσιάζουν από το dict. Όταν η heap συγκρίνει tuples ίσου κόστους, οι κόμβοι πρέπει να μπορούν να συγκριθούν μεταξύ τους ή να χρησιμοποιηθεί tie-breaker counter.

Δοκιμές

1. Πρόσθεσε self-loop βάρους 0. Δεν πρέπει να δημιουργείται συνεχής βελτίωση της ίδιας απόστασης.
2. Πρόσθεσε προσβάσιμη αρνητική ακμή. Η συνάρτηση δίνει ValueError· δεν υποστηρίζει αρνητικά shortest paths.
3. Βάλε αρνητική ακμή σε αποσυνδεδεμένο τμήμα. Ίσως δεν εξεταστεί ποτέ, άρα η υλοποίηση δεν ελέγχει εκ των προτέρων ολόκληρο τον γράφο.
4. Δοκίμασε δύο ισότιμα μονοπάτια. Η απόσταση πρέπει να είναι σωστή, όχι απαραίτητα κάποια συγκεκριμένη επιλογή predecessor.
5. Ξεκίνα από κόμβο χωρίς adjacency. Το αποτέλεσμα περιέχει αυτόν με απόσταση 0.

Επέκταση

Αποθήκευσε predecessor σε κάθε επιτυχημένη relaxation για ανακατασκευή διαδρομής. Για αρνητικά βάρη μελέτησε Bellman–Ford και κύκλους. Με binary heap το συνηθισμένο κόστος είναι O((V+E)log V), με πιθανό χώρο heap ανάλογο του αριθμού relaxations.

10 dijkstra — έλεγχος ορίων

Η Dijkstra επιλέγει πρώτα τη μικρότερη προσωρινή απόσταση. Η ουρά μπορεί να περιέχει παλιές εγγραφές· ο έλεγχος cost != dist[node] τις αγνοεί. Αρνητικά βάρη ακυρώνουν τη λογική της μεθόδου.

Μη προσβάσιμοι κόμβοι λείπουν από τον πίνακα αποστάσεων. Έλεγξε ακμές βάρους μηδέν και διαδρομή που βελτιώνεται μετά από αρχική ακριβότερη διαδρομή.

<!-- [curated-algorithm-detail:10_dijkstra.md] -->

Παρωχημένες εγγραφές ουράς προτεραιότητας στον Dijkstra

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

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

import heapq
graph = {"a":[("b",9),("c",1)], "b":[], "c":[("b",2)]}
assert all(weight >= 0 for edges in graph.values() for _,weight in edges)
best = {"a":0}; heap = [(0,"a")]
while heap:
    cost,node = heapq.heappop(heap)
    if cost != best[node]: continue
    for nxt,weight in graph[node]:
        candidate = cost + weight
        if candidate < best.get(nxt,float("inf")):
            best[nxt] = candidate
            heapq.heappush(heap,(candidate,nxt))
assert best["b"] == 3
print(best)

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

Τεχνική αναφορά