Suunnatussa graafissa (digraph) särmillä on suunta (A → B ≠ B → A). Painotetussa graafissa jokaisella särmällä on numeerinen kosto (etäisyys, aika, kapasiteetti). Molempien yhdistelmä mallintaa todellisuuden järjestelmiä, joissa suhteet ovat yksisuuntaisia ja joilla on kustannus.
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.
| Alue | Solmut | Painotetut suunnatut särmät |
|---|---|---|
| Kartat / GPS | risteyskset | yksisuuntaiset tiet + matka-aika |
| Verkot | reittimet | yhteydet + viive/kaistanleveys |
| Tehtävien ajoitus | tehtävät | riippuvuudet + kestot |
| Rahoitus | valuutat | valuuttakurssit |
| Tavoite | Algoritmi | Kompleksisuus |
|---|---|---|
| Lyhin polku (ei-negatiiviset painot) | Dijkstra | O((V+E) log V) |
| Lyhin polku (negatiiviset särmät) | Bellman-Ford | O(VE) |
| Järjestäminen riippuvuuksilla | Topological sort | O(V+E) |
| Syklien havaitseminen / saavutettavuus | DFS | O(V+E) |
Suunta ja paino muuntavat abstraktin graafin uskolliseksi malliksi reititys-, ajoitus- ja riippuvuusongelmista, jotka ohjaavat oikean maailman sovelluksia.
Algoritmin valinta riippuu näistä ominaisuuksista — esimerkiksi negatiiviset painot sulkevat pois Dijkstran ja vaativat Bellman-Fordin.