U usmjerenom grafu (digraf), grane imaju smjer (A → B ≠ B → A). U ponderiranom grafu, svaka grana nosi numeričku cijenu (udaljenost, vrijeme, kapacitet). Kombinacijom obojega modeliramo stvarne sustave gdje su odnosi jednosmjerni i imaju cijenu.
U usmjerenom grafu (digraf), grane imaju smjer (A → B ≠ B → A). U ponderiranom grafu, svaka grana nosi numeričku cijenu (udaljenost, vrijeme, kapacitet). Kombinacijom obojega modeliramo stvarne sustave gdje su odnosi jednosmjerni i imaju cijenu.
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.
| Domena | Vrhovi | Ponderirane usmjerene grane |
|---|---|---|
| Karte / GPS | raskrižja | jednosmjerne ceste + vrijeme putovanja |
| Mreže | usmjerivači | veze + latencija/propusnost |
| Raspoređivanje zadataka | zadaci | ovisnosti + trajanja |
| Financije | valute | tečajni koeficijenti |
| Cilj | Algoritam | Složenost |
|---|---|---|
| Najkraći put (nenegativne težine) | Dijkstra | O((V+E) log V) |
| Najkraći put (negativne grane) | Bellman-Ford | O(VE) |
| Uređenje s ovisnostima | Topološko sortiranje | O(V+E) |
| Detektiranje ciklusa / dostižnost | DFS | O(V+E) |
Smjer i težina su ono što apstraktni graf pretvara u vjeran model rutiranja, raspoređivanja i problema ovisnosti koji pokrede stvarne aplikacije.
Izbor algoritma ovisi o tim svojstvima — primjerice, negativne težine isključuju Dijkstrin algoritam i zahtijevaju Bellman-Fordov algoritam.