Në një graf të drejtuar (digraf), skajet kanë një drejtim (A → B ≠ B → A). Në një graf të ponderuar, çdo skaj ka një (distancë, kohë, kapacitet). Kombinimi i të dyjave modelon sisteme reale ku marrëdhëniet janë njëdrejtimore dhe kanë një kosto.
Në një graf të drejtuar (digraf), skajet kanë një drejtim (A → B ≠ B → A). Në një graf të ponderuar, çdo skaj ka një (distancë, kohë, kapacitet). Kombinimi i të dyjave modelon sisteme reale ku marrëdhëniet janë njëdrejtimore dhe kanë një kosto.
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.
| Fusha | Kulmet | Skajet e ponderuar dhe të drejtuar |
|---|---|---|
| Hartë / GPS | kryqëzime | rrugë njëdrejtimore + kohë udhëtimi |
| Rrjete | routerë | lidhje + vonesë/gjerësia e brezit |
| Planifikimi i detyrave | detyra | varësi + zgjatje kohe |
| Financa | valuta | kurse këmbimi |
| Qëllimi | Algoritmi | Kompleksitet |
|---|---|---|
| Shtegu më i shkurtër (pesha jo-negative) | Dijkstra | O((V+E) log V) |
| Shtegu më i shkurtër (skajet negative) | Bellman-Ford | O(VE) |
| Renditja me varësi | Renditje topologjike | O(V+E) |
| Zbulimi i cikleve / arritje | DFS | O(V+E) |
Drejtimi dhe pesha janë ato që e shndërrojnë një graf abstrakt në një model të besuar të problemeve të rutimit, planifikimit dhe varësisë që drejtojnë aplikacione reale.
Zgjedhja e algoritmit varet nga këto veti — për shembull, peshat negative eliminojnë Dijkstrën dhe kërkojnë Bellman-Ford.