I graif threoraithe (digraph), tá treo ag na himill (A → B ≠ B → A). I graif ualaithe, iompraíonn gach imeall (fad, am, acmhainneacht). Nuair a chuirtear an dá rud le chéile, modelaítear córais fhíorgheal ina bhfuil gaol aonbhealach ann agus costas aici.
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.
| Fód | Rinn | Imill threoraithe ualaithe |
|---|---|---|
| Léarscáileanna / GPS | crosbhóithre | bóithre aonbhealach + am taistil |
| Líonraí | ródaithe | naisc + fanúchán/bandaleithead |
| Sceidealú tascanna | tascanna | spriocanna + fad ama |
| Airgeadas | airgeadraí | rátaí malartaithe |
| Sprioc | Halgartam | Castacht |
|---|---|---|
| Costas is giorra (meáchain neamhdhiúltach) | Dijkstra | O((V+E) log V) |
| Costas is giorra (imill dhiúltach) | Bellman-Ford | O(VE) |
| Ordú le spriocanna | Sórtáil thopagrafach | O(V+E) |
| Timthriall a bhrath / inrochtaineacht | DFS | O(V+E) |
Is iad an treo agus an t-ualach an méid a dhéanann graf teibí a iompú ina mhúnla fírinneach de fhadhbanna ródúcháin, sceidealúcháin, agus spriocdhíleathnaithe a dhíonann fíorfheidhmchláir.
Bíonn rogha an halgartaim ag brath ar na hairíonna seo — mar shampla, cuireann meáchain dhiúltach isteach ar Dijkstra agus ba dhéan Bellman-Ford a úsáid.