Dijkstra
Συντομότερες διαδρομές από μία κορυφή με μη αρνητικά βάρη, σε .
Πότε
Γράφος με βάρη και ερώτηση «ελάχιστο κόστος από το ». Αν τα βάρη είναι όλα ίσα, αρκεί BFS. Αν υπάρχουν αρνητικά, χρειάζεται Bellman–Ford.
Η ιδέα
Η BFS με σωρό αντί για ουρά. Κάθε φορά βγάζουμε την κορυφή με τη μικρότερη προσωρινή απόσταση. Επειδή τα βάρη δεν είναι αρνητικά, καμία διαδρομή που περνά από κορυφές που δεν έχουν βγει ακόμα δεν μπορεί να είναι μικρότερη. Άρα η απόσταση αυτής της κορυφής είναι τελική.
Η priority_queue της STL δεν έχει decrease-key. Αντί γι' αυτό, βάζουμε ξανά την κορυφή με τη νέα απόσταση και, όταν βγαίνει μια παλιά εγγραφή, την προσπερνάμε: if (d > dist[u]) continue;. Ο σωρός μπορεί να φτάσει τις εγγραφές, αλλά , οπότε η πολυπλοκότητα δεν αλλάζει.
Η κίνηση που ξεκλειδώνει προβλήματα
Γράφος καταστάσεων. Στο Flight Discount μπορείς να χρησιμοποιήσεις ένα κουπόνι μισής τιμής μία φορά. Η κατάσταση είναι το ζευγάρι (πόλη, χρησιμοποίησα το κουπόνι;), δηλαδή κορυφές. Από το πας στο με κόστος και στο με . Ο Dijkstra τρέχει όπως είναι.
Στο Investigation θέλεις, εκτός από το ελάχιστο κόστος, και πόσες ελάχιστες διαδρομές υπάρχουν. Αυτά ενημερώνονται μέσα στη χαλάρωση: σε ισοπαλία προσθέτεις, σε βελτίωση αντικαθιστάς.
Παγίδες
- Η απόσταση σε
long longκαι το «άπειρο»LLONG_MAX. Μην προσθέσεις βάρος στο άπειρο. Ο κώδικας εδώ δεν το κάνει ποτέ, γιατί χαλαρώνει μόνο από κορυφές που έχουν βγει από τον σωρό. - Χωρίς το
continueγια τις παλιές εγγραφές ο αλγόριθμος μένει σωστός, αλλά σε πυκνό γράφο γίνεται στη χειρότερη περίπτωση.
Κώδικας
Χωρίς main: μπαίνει κάτω από τα #include, το using namespace std και το using ll = long long.
// Dijkstra with a binary heap: shortest paths from src, non-negative weights. O((n + m) log n).
// Stale heap entries (d > dist[u]) are skipped instead of decreased.
// Unreachable vertices keep LLONG_MAX.
vector<ll> dijkstra(const vector<vector<pair<int, ll>>>& adj, int src) {
int n = adj.size();
vector<ll> dist(n, LLONG_MAX);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
dist[src] = 0;
pq.push({0, src});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) {
continue;
}
for (auto [v, w] : adj[u]) {
if (d + w < dist[v]) {
dist[v] = d + w;
pq.push({dist[v], v});
}
}
}
return dist;
}
Ελέγχθηκε σε 1.000 τυχαίες περιπτώσεις απέναντι σε αργή, προφανώς σωστή λύση, με AddressSanitizer και UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).
Για εξάσκηση στο CSES
Με τη σειρά: το πρώτο είναι η καθαρή εφαρμογή, τα επόμενα θέλουν μια παραλλαγή.
- Shortest Routes I · Graph Algorithms
- Flight Discount · Graph Algorithms
- Investigation · Graph Algorithms
Περισσότερα στο USACO Guide
- Shortest Paths with Non-Negative Edge Weights · usaco.guide/gold/shortest-paths
Στα αγγλικά, με επιπλέον προβλήματα ανά επίπεδο.