దిశాత్మక గ్రాఫ్లో (digraph), అంచులకు దిశ ఉంటుంది (A → B ≠ B → A). సన్నహిత గ్రాఫ్లో, ప్రతి అంచు సంఖ్యా ఖర్చు (దూరం, సమయం, సామర్థ్యం) కలిగి ఉంటుంది. రెండింటినీ కలపడం వాస్తవ సిస్టమ్లను మోడల్ చేస్తుంది, ఇక్కడ సంబంధాలు ఒక-మార్గం మరియు ఖర్చు కలిగి ఉంటాయి.
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.
| డొమైన్ | శీర్షాలు | సన్నహిత దిశాత్మక అంచులు |
|---|---|---|
| మ్యాప్లు / GPS | ఖండనలు | ఏక-దిశ రోడ్డులు + ప్రయాణ సమయం |
| నెట్వర్క్లు | రౌటర్లు | లింకులు + సుస్తత/బ్యాండ్విడ్త్ |
| పని షెడ్యూలింగ్ | పనులు | ఆధారణలు + చిత్రకాలు |
| ఆర్థిక నిర్వహణ | కరెన్సీలు | మార్పిడి రేట్లు |
| లక్ష్యం | అల్గారిధం | సంక్లిష్టత |
|---|---|---|
| చిన్న మార్గం (ప్రతికూల రహిత భారం) | Dijkstra | O((V+E) log V) |
| చిన్న మార్గం (ప్రతికూల అంచులు) | Bellman-Ford | O(VE) |
| ఆధారణలతో క్రమాన్ని క్రమం చేయడం | సంస్థాపక క్రమీకరణ | O(V+E) |
| చక్రాలు/చేరుకోవడం గుర్తించండి | DFS | O(V+E) |
దిశ మరియు బరువు ఒక నైరూప్య గ్రాఫ్ను రూటింగ్, షెడ్యూలింగ్ మరియు ఆధారణ సమస్యల యొక్క విశ్వసనీయ మోడల్గా మారుస్తాయి, ఇవి నిజమైన అనువర్తనాలను నడిపిస్తాయి.
అల్గారిదం ఎంపిక ఈ లక్షణాలపై ఆధారపడి ఉంటుంది — ఉదాహరణకు, ప్రతికూల బరువులు Dijkstraను మినహాయించి Bellman-Fordను కోరుకుంటాయి.