Σε ένα κατευθυνόμενο γράφημα (digraph), οι ακμές έχουν κατεύθυνση (A → B ≠ B → A). Σε ένα γράφημα, κάθε ακμή φέρει (απόσταση, χρόνος, χωρητικότητα). Η συνδυασμένη χρήση και των δύο μοντελοποιεί πραγματικά συστήματα όπου οι σχέσεις είναι μονόπλευρες και έχουν κόστος.
Weighted directed graph:
A --5--> B
A --2--> C
C --1--> B
Adjacency list with weights:
A: [(B,5), (C,2)]
B: []
C: [(B,1)]
graph = {
'A': [('B', 5), ('C', 2)], # directed, weighted edges
'B': [],
'C': [('B', 1)],
}
# Shortest A->B is A->C->B = 2 + 1 = 3, not the direct edge 5.
| Τομέας | Κορυφές | Σταθμισμένες κατευθυνόμενες ακμές |
|---|---|---|
| Χάρτες / GPS | διασταυρώσεις | δρόμοι μίας κατεύθυνσης + χρόνος ταξιδίου |
| Δίκτυα | δρομολογητές | σύνδεσμοι + καθυστέρηση/εύρος ζώνης |
| Χρονοδιάγραμμα εργασιών | εργασίες | εξαρτήσεις + διάρκειες |
| Χρηματοοικονομικά | νομίσματα | ισοτιμίες |
| Στόχος | Αλγόριθμος | Πολυπλοκότητα |
|---|---|---|
| Συντομότερη διαδρομή (μη αρνητικά βάρη) | Dijkstra | O((V+E) log V) |
| Συντομότερη διαδρομή (αρνητικές ακμές) | Bellman-Ford | O(VE) |
| Ταξινόμηση με εξαρτήσεις | Topological sort | O(V+E) |
| Ανίχνευση κύκλων / προσβασιμότητα | DFS | O(V+E) |
Η κατεύθυνση και το βάρος είναι αυτά που μετατρέπουν ένα αφηρημένο γράφημα σε ένα πιστό μοντέλο προβλημάτων δρομολόγησης, χρονοδιαγράμματος και εξάρτησης που οδηγούν πραγματικές εφαρμογές.
Η επιλογή του αλγόριθμου εξαρτάται από αυτές τις ιδιότητες — για παράδειγμα, τα αρνητικά βάρη αποκλείουν τον Dijkstra και απαιτούν τον Bellman-Ford.