નિર્દેશિત ગ્રાફમાં (digraph), કિનારીઓને દિશા હોય છે (A → B ≠ B → A). વજનિત ગ્રાફમાં, દરેક કિનારી આંકડાત્મક કિંમત વહન કરે છે (અંતર, સમય, ક્ષમતા). બંનેને મિશ્રણ કરવાથી વાસ્તવિક સિસ્ટમ્સ મોડેલ થાય છે જ્યાં સંબંધો એક-માર્ગી હોય અને તેમની કિંમત હોય.
નિર્દેશિત ગ્રાફમાં (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 ની જરૂર પડે છે.