في الرسم البياني الموجه (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.
| المجال | الرؤوس | الحواف الموجهة الموزونة |
|---|---|---|
| الخرائط / نظام تحديد المواقع | التقاطعات | طرق أحادية الاتجاه + وقت السفر |
| الشبكات | أجهزة التوجيه | الروابط + الكمون/النطاق الترددي |
| جدولة المهام | المهام | التبعيات + المدد |
| التمويل | العملات | أسعار الصرف |
| الهدف | الخوارزمية | التعقيد |
|---|---|---|
| أقصر مسار (أوزان غير سالبة) | Dijkstra | O((V+E) log V) |
| أقصر مسار (حواف سالبة) | Bellman-Ford | O(VE) |
| الترتيب مع التبعيات | Topological sort | O(V+E) |
| الكشف عن الدورات / القابلية للوصول | DFS | O(V+E) |
الاتجاه والوزن هما ما يحولان الرسم البياني المجرد إلى نموذج دقيق للتوجيه والجدولة ومشاكل التبعيات التي تقود التطبيقات الحقيقية.
يتوقف اختيار الخوارزمية على هذه الخصائص — على سبيل المثال، الأوزان السالبة تستبعد Dijkstra وتتطلب Bellman-Ford.