V usmerjenem grafu (digraf) imajo robovi smer (A → B ≠ B → A). V tehtanem grafu ima vsak rob numerično ceno (razdalja, čas, kapaciteta). Kombinacija obeh modelira prave sisteme, kjer so odnosi enosmerani in imajo ceno.
V usmerjenem grafu (digraf) imajo robovi smer (A → B ≠ B → A). V tehtanem grafu ima vsak rob numerično ceno (razdalja, čas, kapaciteta). Kombinacija obeh modelira prave sisteme, kjer so odnosi enosmerani in imajo ceno.
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.
| Področje | Vozlišča | Tehtani usmerjeni robovi |
|---|---|---|
| Zemljevidi / GPS | križišča | enosmernih cest + čas potovanja |
| Omrežja | usmerjevalniki | povezave + zakasnitve/pasovna širina |
| Razporejanje nalog | naloge | odvisnosti + trajanja |
| Finance | valute | tečaji |
| Cilj | Algoritem | Časovna zahtevnost |
|---|---|---|
| Najkrajša pot (nenegativne teže) | Dijkstra | O((V+E) log V) |
| Najkrajša pot (negativni robovi) | Bellman-Ford | O(VE) |
| Uređanje z odvisnostmi | Topološko sortiranje | O(V+E) |
| Zaznava ciklov / dosegljivost | DFS | O(V+E) |
Smer in teža sta tista, ki iz abstraktnega grafa naredita zvesto predstavo problemov usmerjanja, razporejanja in odvisnosti, ki poganjajo prave aplikacije.
Izbira algoritma je odvisna od teh lastnosti — na primer negativne teže izključijo Dijkstro in zahtevajo Bellman-Ford.