W skierowanym grafie (digraph) krawędzie mają kierunek (A → B ≠ B → A). W ważonym grafie każda krawędź nosi liczbowy koszt (odległość, czas, pojemność). Kombinacja obu modeluje rzeczywiste systemy, w których relacje są jednokierunkowe i wiążą się z kosztem.
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.
| Dziedzina | Wierzchołki | Ważone krawędzie skierowane |
|---|---|---|
| Mapy / GPS | skrzyżowania | drogi jednokierunkowe + czas podróży |
| Sieci | routery | połączenia + opóźnienie/przepustowość |
| Planowanie zadań | zadania | zależności + czasy trwania |
| Finanse | waluty | kursy wymiany |
| Cel | Algorytm | Złożoność |
|---|---|---|
| Najkrótsza ścieżka (wagi nieujemne) | Dijkstra | O((V+E) log V) |
| Najkrótsza ścieżka (krawędzie ujemne) | Bellman-Ford | O(VE) |
| Porządkowanie z zależnościami | Topological sort | O(V+E) |
| Wykrywanie cykli / osiągalność | DFS | O(V+E) |
Kierunek i waga to to, co przekształca abstrakcyjny graf w wierny model problemów routingu, planowania i zależności, które napędzają rzeczywiste aplikacje.
Wybór algorytmu zależy od tych właściwości — na przykład wagi ujemne eliminują Dijkstrę i wymagają Bellmana-Forda.