حل مشكلة إيجاد أقصر طريق باستخدام خوارزمية ديكسترا.
ابحث عن أقصر طريق من X0 إلى X7. يتم إعطاء الرسم البياني بواسطة عناصر مصفوفة التكلفة
دعونا نبني هذا الرسم البياني 
لنبدأ بالعنصر X0 ونخصص له تسمية 0 ، ضع في اعتبارك جميع جيرانه ، منذ ذلك الحين لا توجد علامات بعد ، ثم نخصص لها الأطوال المناسبة: 
يتم اعتبار جميع الأجهزة المجاورة X0 ، ونضع علامة عليها ونذهب إلى الرأس X1. جيرانها X0 ، X2 ، X4 ، ولكن X0 تم وضع علامة عليها ، نحن لا نعتبرها. بالنسبة لـ X2: 
، اترك الملصق.
بالنسبة إلى X4: 
، استبدل الملصق. يتم اعتبار جميع جيران الرأس X1 ، ونضع علامة عليها 
انتقل إلى أعلى X2. جيران ITS X0 و X1 و X3 و X4 و X5 و X6 ولكن تم وضع علامة على X0 و X1 ، ونحن لا نعتبرهم.
بالنسبة لـ X3: 
، اترك الملصق.
بالنسبة لـ X5: 
، استبدل الملصق.
بالنسبة إلى X4: 
، اترك الملصق.
بالنسبة لـ X6: 
، استبدل الملصق.
تم اعتبار جميع الأجهزة المجاورة لـ vertex X2 ، ونضع علامة عليها. 
انتقل إلى أعلى X3. جيران ITS X0 و X2 و X6 ولكن X0 و X2 تم وضع علامة عليهم ، ونحن لا نعتبرهم.
بالنسبة لـ X6: 
، اترك الملصق.
تم النظر في جميع الأجهزة المجاورة لـ vertex X3 ، ونضع علامة عليها. 
انتقل إلى أعلى X4. جيران ITS X1 و X2 و X5 و X7 ولكن تم وضع علامة على X1 و X2 ، ونحن لا نعتبرهم.
بالنسبة لـ X5: 
، استبدل الملصق.
بالنسبة لـ X7: 
، استبدل الملصق.
تم النظر في جميع الأجهزة المجاورة لـ Vertex X4 ، ونضع علامة عليها. 
انتقل إلى أعلى X5. جيران ITS X2 و X4 و X6 و X7 ولكن تم وضع علامة على X2 و X4 ، ونحن لا نعتبرهم.
بالنسبة لـ X6: 
، اترك الملصق.
بالنسبة لـ X7: 
، اترك الملصق.
تم النظر في جميع الأجهزة المجاورة لـ vertex X5 ، ونضع علامة عليها. 
اذهب إلى الأعلى X6. تم وضع علامة على جيرانها X2 و X3 و X5 و X7 ولكن X2 و X3 و X5 ، ونحن لا نعتبرهم.
بالنسبة لـ X7: 
، اترك الملصق.
تم النظر في جميع الأجهزة المجاورة لـ vertex X6 ، ونضع علامة عليها. ونضع علامة على X7 المتبقية ، يتم أخذ جميع الرؤوس في الاعتبار. 
الخلاصة: أقصر مسار من X0 إلى X7 يبلغ طوله 101 ، هذا المسار: X7-X4-X1-X0.
فكر في مثال لإيجاد أقصر طريق. تم توفير شبكة من الطرق السريعة التي تربط مناطق المدينة. بعض الطرق ذات اتجاه واحد. ابحث عن أقصر الطرق من وسط المدينة إلى كل مدينة في المنطقة.
لحل هذه المشكلة ، يمكنك استخدام خوارزمية ديكسترا- خوارزمية على الرسوم البيانية اخترعها العالم الهولندي E.Dijkstroy في عام 1959. يكتشف أقصر مسافة من أحد رؤوس الرسم البياني إلى جميع الرؤوس الأخرى. يعمل فقط مع الرسوم البيانية بدون حواف ذات وزن سالب.
دع الأمر مطلوبًا للعثور على أقصر المسافات من الرأس الأول إلى جميع الرؤوس الأخرى.
تشير الدوائر إلى الرؤوس ، بينما تشير الخطوط إلى المسارات بينها (حواف الرسم البياني). تشير الدوائر إلى عدد الرؤوس ، فوق الحواف يُشار إلى وزنها - طول المسار. يوجد بجانب كل رأس تسمية حمراء - طول أقصر مسار لهذا الرأس من الرأس 1.
تم تعيين تسمية الرأس 1 نفسها مساوية لـ 0 ، وتسميات الرؤوس المتبقية هي رقم لا يمكن الوصول إليه (من الناحية المثالية ، اللانهاية). وهذا يعكس حقيقة أن المسافات من القمة 1 إلى القمم الأخرى لم تُعرف بعد. تم تمييز جميع رؤوس الرسم البياني على أنها لم تتم رؤيتها. 
الخطوة الأولى
الرأس 1 له الحد الأدنى من التسمية ، وجيرانه هم الرؤوس 2 و 3 و 6. نلتف حول جيران الرأس بدورنا.
الجار الأول للرأس 1 هو الرأس 2 ، لأن طول المسار إليه ضئيل. طول المسار المؤدي إليه عبر الرأس 1 يساوي مجموع أقصر مسافة للرأس 1 ، وقيمة التسمية ، وطول الحافة التي تنتقل من 1 إلى 2 ، أي 0 + 7 = 7. هذا أقل من التسمية الحالية للرأس 2 (10000) ، وبالتالي فإن التسمية الجديدة للرأس الثاني هي 7. 
وبالمثل ، نجد أطوال المسار لجميع الجوار الآخرين (الرؤوس 3 و 6).
يتم فحص جميع جيران الرأس 1. تعتبر المسافة الدنيا الحالية للذروة 1 نهائية ولا تخضع للمراجعة. تم وضع علامة على الذروة 1 على أنها تمت زيارتها.
الخطوة الثانية
يتم تكرار الخطوة 1 من الخوارزمية. ابحث عن "أقرب" الرؤوس غير المرئية مرة أخرى. هذا هو الرأس 2 ، المسمى 7.
نحاول مرة أخرى تقليل تسميات جيران الرأس المحدد ، محاولين المرور من خلال الرأس الثاني. جيران الرأس 2 هم الرؤوس 1 و 3 و 4.
تمت زيارة Vertex 1 بالفعل. الجار التالي للقمة 2 هو الرأس 3 ، حيث أنه يحتوي على الحد الأدنى من تسمية القمم التي تم تمييزها على أنها لم تتم زيارتها. إذا انتقلت إليه من خلال 2 ، فسيكون طول هذا المسار مساويًا لـ 17 (7 + 10 = 17). لكن التسمية الحالية للرأس الثالث هي 9 و 9< 17, поэтому метка не меняется.
الجار الآخر للرأس 2 هو الرأس 4. إذا انتقلت إليه من خلال الثاني ، فسيكون طول هذا المسار مساويًا لـ 22 (7 + 15 = 22). منذ 22<10000, устанавливаем метку вершины 4 равной 22.
تم عرض جميع جيران الرأس 2 ، ونضع علامة عليها على أنها تمت زيارتها.
خطوة ثالثة
نكرر خطوة الخوارزمية باختيار قمة الرأس 3. وبعد "معالجتها" نحصل على النتائج التالية. 
الخطوة الرابعة
الخطوة الخامسة
الخطوة السادسة
وبالتالي ، فإن أقصر مسار من الرأس 1 إلى الرأس 5 سيكون المسار عبر الرؤوس 1 — 3 — 6 — 5
لأننا بهذه الطريقة نحصل على وزن لا يقل عن 20.
دعونا نتناول اشتقاق أقصر طريق. نحن نعرف طول المسار لكل رأس ، والآن سننظر في الرؤوس من النهاية. ضع في اعتبارك الرأس الأخير (في هذه الحالة ، الرأس 5
) ، وبالنسبة لجميع الرؤوس المتصلة بها ، نجد طول المسار بطرح وزن الحافة المقابلة من طول مسار الرأس النهائي.
لذا ، فإن القمة 5
له طول المسار 20
... هي متصلة بالقمم 6
و 4
.
في القمة 6
احصل على الوزن 20-9 = 11 (مطابق).
في القمة 4
احصل على الوزن 20-6 = 14 (غير متطابق).
نتيجة لذلك ، إذا حصلنا على قيمة تتطابق مع طول مسار الرأس المدروس (في هذه الحالة ، الرأس 6
) ، ثم من هذه النقطة تم الانتقال إلى القمة النهائية. نحتفل بهذه الذروة على المسار المطلوب.
بعد ذلك ، نحدد الحافة التي وصلنا من خلالها إلى الرأس 6
... وهكذا حتى نصل إلى البداية.
إذا كان لدينا ، نتيجة لمثل هذا الاجتياز ، في خطوة ما نفس القيم للعديد من الرؤوس ، فيمكننا إذن اتخاذ أي منها - سيكون للعديد من المسارات نفس الطول.
تنفيذ خوارزمية ديكسترا
تستخدم المصفوفة المربعة لتخزين أوزان الرسم البياني. تحتوي عناوين الصفوف والأعمدة على رؤوس الرسم البياني. ويتم وضع أوزان أقواس الرسم البياني في الخلايا الداخلية للجدول. لا يحتوي الرسم البياني على حلقات ؛ لذلك ، يحتوي القطر الرئيسي للمصفوفة على قيم صفرية.
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | 0 | 7 | 9 | 0 | 0 | 14 |
| 2 | 7 | 0 | 10 | 15 | 0 | 0 |
| 3 | 9 | 10 | 0 | 11 | 0 | 2 |
| 4 | 0 | 15 | 11 | 0 | 6 | 0 |
| 5 | 0 | 0 | 0 | 6 | 0 | 9 |
| 6 | 14 | 0 | 2 | 0 | 9 | 0 |
تطبيق C ++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#define _CRT_SECURE_NO_WARNINGS
#يشمل
#يشمل
#define SIZE 6
انت مين ()
{
الباحث أ ؛ // مصفوفة الروابط
كثافة العمليات د ؛ // الحد الأدنى للمسافة
في التلفاز؛ // القمم التي تمت زيارتها
int temp ، minindex ، دقيقة ؛
int start_index = 0 ؛
نظام ("chcp 1251") ؛
النظام ("cls") ؛
// تهيئة مصفوفة الروابط
لـ (int i = 0 ؛ i
أ [i] [i] = 0 ؛
لـ (int j = i + 1 ؛ j
scanf ("٪ d" ، & درجة الحرارة) ؛
أ [i] [j] = درجة الحرارة ؛
a [j] [i] = temp ؛
}
}
// عرض مصفوفة الروابط
لـ (int i = 0 ؛ i
لـ (int j = 0 ؛ j
printf ("\ n") ؛
}
// تهيئة الرؤوس والمسافات
لـ (int i = 0 ؛ i
د [i] = 10000 ؛
الخامس [i] = 1 ؛
}
د = 0 ؛
// خطوة الخوارزمية
فعل (
مينديكس = 10000 ؛
دقيقة = 10000 ؛
لـ (int i = 0 ؛ i
إذا ((v [i] == 1) && (d [i]
دقيقة = d [i] ؛
مينينديكس = أنا ؛
}
}
// أضف الوزن الأدنى الموجود
// للوزن الحالي للرأس
// ويقارن مع الوزن الأدنى الحالي للرأس
إذا كان (ميندكس! = 10000)
{
لـ (int i = 0 ؛ i
إذا (a [i]> 0)
{
temp = min + a [i] ؛
إذا (temp< d[i])
{
د [i] = درجة الحرارة ؛
}
}
}
الخامس = 0 ؛
}
) بينما (minindex< 10000);
// عرض أقصر المسافات للرؤوس
printf ( "\ n أقصر مسافة للوصول إلى الذروة: \ n");
لـ (int i = 0 ؛ i
// استعادة المسار
نسخة int // مجموعة من القمم التي تمت زيارتها
نهاية int = 4 ؛ // فهرس الرأس النهائي = 5-1
الإصدار = النهاية + 1 ؛ // عنصر البداية - قمة الرأس
كثافة العمليات ك = 1 ؛ // فهرس الرأس السابق
الوزن int = d ؛ // وزن الرأس النهائي
بينما (النهاية! = start_index) // لم تصل بعد إلى القمة الأولية
{
لـ (int i = 0 ؛ i
إذا (a [i]! = 0) // إذا كان هناك اتصال
{
int temp = الوزن - a [i] ؛ // تحديد وزن المسار من الرأس السابق
إذا (temp == d [i]) // إذا تزامن الوزن مع المحسوب
{ // يعني أنه من هذا الرأس كان هناك انتقال
الوزن = درجة الحرارة // احفظ الوزن الجديد
النهاية = أنا ؛ // حفظ الرأس السابق
ver [k] = i + 1 ؛ // واكتبها في مصفوفة
ك ++ ؛
}
}
}
// إخراج المسار (كان الرأس الأولي في نهاية مصفوفة من عناصر k)
printf ( "\ n عرض أقصر مسار \ n");
لـ (int i = k - 1 ؛ i> = 0 ؛ i--)
printf ("٪ 3d" ، الإصدار [i]) ؛
getchar () ؛ getchar () ؛
العودة 0 ؛
}
نتيجة التنفيذ
خلف:
تم تصميم خوارزمية Dijkstra للعثور على أقصر مسار بين الرؤوس في رسم بياني غير موجه.
فكرة الخوارزمية هي كما يلي: أولاً ، نختار المسار إلى الرأس الأولي الذي يساوي صفرًا وندخل هذا الرأس في مجموعة الرؤوس المحددة بالفعل ، ويتم تحديد المسافة التي من خلالها إلى الرؤوس غير المحددة المتبقية. في كل مرحلة تالية ، نجد الرأس المحدد التالي ، والمسافة التي هي الأصغر ، ومتصلة بحافة إلى رأس ما من مجموعة غير المختارة (هذه المسافة ستكون مساوية للمسافة إلى الرأس المحدد بالإضافة إلى الطول من الحافة).
مثال 1.ابحث عن أقصر مسار على الرسم البياني من الرأس إلالى القمة د(شكل 10.7).
أرز. 10.7.
دعنا نكتب الخوارزمية في شكل سلسلة من الخطوات (الجدول 10.1). خطوة 1. حدد المسافة من الرأس الأولي إلقبل أي شخص آخر.
الجدول 10.1
طريقة ديكسترا (الخطوة الأولى)
|
المحدد |
المسار إلى الرأس المحدد |
قمة غير محددة |
|||||||
خطوة 2. اختر أصغر مسافة من إلقبل الخامس؛وجدت الذروة الخامسيؤخذ على أنه تم تحديده حديثًا. تتم إضافة أصغر مسافة تم العثور عليها إلى أطوال الحواف من الرأس الجديد الخامسقبل أي شخص آخر. نختار الحد الأدنى للمسافة من الخامسقبل ن.ذروة جديدة ننأخذ للمختار (الجدول 10.2).
الجدول 10.2
طريقة ديكسترا (الخطوة الثانية)
|
المحدد |
المسار إلى الرأس المحدد |
قمة غير محددة |
|||||||
من أجل الوضوح ، فيما يلي ، بدلاً من علامة oo ، سنضع علامة "-".
خطوة 3. تحديد المسافة من الأعلى ن لعن كل ما تبقى (باستثناء إلو الخامس)،كما هو مبين في الجدول. 10.3.
الجدول 10.3
طريقة ديكسترا (الخطوة الثالثة)
|
المحدد |
المسار إلى الرأس المحدد |
قمة غير محددة |
|||||||
المسافة من الأعلى إلفي الجزء العلوي N إلىقمم جييساوي 18 وحدة تقليدية. هذه المسافة أكبر من المسافة LB + BG= 16 وحدة تقليدية ، ونتيجة لذلك لا يتم أخذها في الاعتبار في المستقبل. استمرار الإنشاءات المماثلة ، سنقوم بتجميع الجدول. 10.4. وهكذا ، تم العثور على طول أقصر مسار بين القمم إلو د(44 وحدة تقليدية).
يتم تحديد مسار المسار على النحو التالي. نجري بحثًا عكسيًا من الرأس الأخير إلى الرأس الأول. ننظر من خلال العمود المقابل للأعلى من الأسفل إلى الأعلى ونصلح التكرار الأول للحد الأدنى للقيمة. في العمود المقابل للرأس د،لأول مرة ظهر الحد الأدنى للطول البالغ 44 وحدة تقليدية في أسفل السطر الرابع. يشير هذا الخط إلى الرأس س،إلى أي واحد يجب أن يذهب ، أي بعد ذلك ، نحتاج إلى النظر في العمود المقابل للرأس س.
الجدول 10.4
|
الرأس المحدد |
المسار إلى الرأس المحدد |
قمة غير محددة |
|||||||
في هذا العمود ، يشير الحد الأدنى للطول البالغ 27 وحدة تقليدية إلى الرأس التالي زإلى أي واحد يجب أن يذهب ، إلخ. وهكذا نحصل على مسار المسار: (L ، B ، G ، S ، D).
المثال 8.ابحث عن أقصر مسار على الرسم البياني بين الرأسين الأول والسابع (الشكل 10.8).
حدد (الجدول 10.5) الرأس المحدد التالي ، المسافة التي هي الأصغر والمتصلة بحافة بأحد الرؤوس التي تنتمي إلى مجموعة الرؤوس غير المحددة (هذه المسافة ستكون مساوية للمسافة إلى الرأس المحدد بالإضافة إلى الطول من الحافة).
أرز. 10.8. رسم بياني (أ)والمصفوفة المجاورة المقابلة (ب)
تنفيذ جدولي لطريقة ديكسترا
الجدول 10.5
|
المحدد |
المسار إلى الرأس المحدد |
قمة غير محددة |
||||||
|
في 6 |
||||||||
نجري بحثًا عكسيًا من الرأس الأخير إلى الرأس الأول.
ننظر من خلال العمود المقابل للأعلى من الأسفل إلى الأعلى ونصلح التكرار الأول للحد الأدنى للقيمة. سيكون أقصر طريق في هذه الحالة متساويًا (الخامس 7 - الخامس 5 - الخامس 2 - ص ().
وأسئلة التحكم
- 1. ما هو التعقيد النظري للخوارزميات: بناء شجرة قرار ، برمجة ديناميكية و Dijkstra؟
- 2. ما هي خصوصية استخدام شجرة القرار للرسوم البيانية الموجهة وغير الموجهة؟
- 3. في حل ما هي المشاكل المطبقة هي خوارزميات لتحديد أقصر المسافات بين القمم المعطاة في الرسم البياني؟
- 4. هل يمكن تطبيق خوارزمية Dijkstra في العمل لتحديد أقصر مسافة في الرسم البياني الموجه؟
- 5. كيف تعمل خوارزمية Dijkstra؟
- 6. كيف تعمل خوارزمية البرمجة الديناميكية فيما يتعلق بمشكلة تحديد أقصر المسافات بين الرؤوس في الرسم البياني؟
خوارزمية Dijkstra هي خوارزمية رسم بياني تجد أقصر مسار بين رأسين معينين في رسم بياني بأطوال قوسية غير سالبة. أيضًا ، غالبًا ما يتم طرح مهمة حساب أقصر مسار من قمة معينة إلى جميع المسارات الأخرى. تستخدم الخوارزمية على نطاق واسع في البرمجة ، على سبيل المثال ، يتم استخدامها بواسطة بروتوكولات التوجيه.
وصف
مدخلات الخوارزمية عبارة عن رسم بياني موجه مرجح بأقواس ذات وزن غير سالب. الإخراج عبارة عن مجموعة من أقصر المسارات من هذا الرأس إلى الآخرين.
في البداية ، يُفترض أن تكون المسافة للرأس الأولي صفرًا ، ويُفترض أن تكون المسافات إلى كل الآخرين غير محدودة. مصفوفة من الأعلام تشير إلى ما إذا كان الرأس قد تم تمريره ممتلئًا بالأصفار. بعد ذلك ، في كل خطوة من الدورة ، يتم البحث عن رأس بمسافة دنيا عن الأولى وعلم يساوي الصفر. يتم تعيين علم له ويتم فحص جميع القمم المجاورة. إذا كانت المسافة المحسوبة مسبقًا من الرأس الأصلي إلى الرأس المحدد أكبر من مجموع المسافة إلى الرأس الحالي وطول الحافة منه إلى الرأس المحدد ، فإن المسافة إلى الرأس المحدد تساوي المسافة إلى الرأس الحالي + الحافة من التيار إلى الرأس المحدد. تنتهي الدورة عندما تصبح أعلام جميع الرؤوس مساوية لـ 1 ، أو عندما تكون المسافة إلى جميع القمم ذات العلم 0 غير محدودة. تكون الحالة الأخيرة ممكنة إذا وفقط إذا تم فصل الرسم البياني.
خوارزمية ديكسترا في الكود الكاذب
مدخل: مع: مصفوفة حقيقية من أطوال أقواس الرسم البياني ؛ s هو الرأس الذي منه يتم البحث عن أقصر مسار و t هي القمة التي يتم البحث عنها.
الإخراج: المتجهات T: مجموعة حقيقية ؛ و H: صفيف من 0..r. إذا كان الجزء العلوي الخامستقع على أقصر طريق من سإلى رمن ثم تلفزيون]- أقصر مسار من سإلى ذ ؛ حسنا] -رأس التي تسبق مباشرة فيعلى أقصر طريق.
H - مصفوفة يتوافق فيها الرأس n مع الرأس m ، والسابقة في الطريق إلى n من s.
T هي مصفوفة يقابل فيها الرأس n المسافة منه إلى s.
X عبارة عن مصفوفة يقابل فيها الرأس n 1 إذا كان المسار إليها معروفًا ، و 0 إذا لم يكن كذلك.
تهيئة المصفوفات:
ل الخامسمن 1 الى صفعل
تي [الخامس]: = ∞ (أقصر مسار غير معروف)
X [v]: = 0 (جميع الرؤوس غير محددة)
ح [ق]: = 0 ( س لا شيء يأتي من قبل)
T [s]: = 0 (أقصر مسار له طول 0 ...)
X [s]: = 1 (... وهو معروف) الخامس : = س (الذروة الحالية)
م: (ملاحظات التحديث)
ل و ∈ G ( و) فعل
لو X [و] = 0 & T [و]> تلفزيون] + جمن ثم
تي [ش]: = تلفزيون] + ج(تم العثور على مسار أقصر من س الخامس وعير الخامس }
ح [ش]:= الخامس(تذكر ذلك)
م: = ∞
الخامس : = 0
(إيجاد نهاية أقصر طريق)
ل ومن 1 الى ص فعل
لو X [u] = 0 & ت [ش]< رمن ثم
الخامس:= ش;
م:= تي [ش](أعلى الخامس ينتهي أقصر طريق من س
لو الخامس = 0 بعد ذلك
توقف (بأي حال من الأحوال من س الخامس ر) إنهاء إذا
لو الخامس= رمن ثم
توقف (أقصر مسار تم العثور عليه من س الخامس ر) إنهاء إذا
X [v]: = 1 (تم العثور على أقصر مسار من س الخامس الخامس ) اذهب إلى م
التبرير
لإثبات صحة خوارزمية Dijkstra ، يكفي ملاحظة أنه لكل تنفيذ لجسم الدورة يبدأ بالعلامة M ، مثل الخامسالرأس الذي يستخدم أقصر مسار معروف من القمة س.بعبارة أخرى ، إذا كانت X [v] = 1 ، فإن T [v] = d (s ، v) , وجميع الرؤوس على المسار (s ، v) المحددة بواسطة المتجه H لها نفس الخاصية ، أي
Vu T [u] = 1 => T [u] = d (s، u) & T] = 1.
بالفعل (عن طريق الاستقراء) ، لأول مرة كما الخامسيتم استخدام قمة الرأس حيث يكون أقصر مسار فارغًا وطوله 0 (لا يمكن أن تكون المسارات غير الفارغة أقصر ، لأن أطوال الأقواس غير سالبة). دع T [u] = d (s، u) لجميع القمم المحددة مسبقًا و.ضع في اعتبارك قمة الرأس المميزة حديثًا الخامس، والذي يتم تحديده من الشرط T [v] = min T [u]. لاحظ أنه إذا كان المسار الذي يمر عبر القمم المحددة معروفًا ، فإن أقصر مسار يكون معروفًا. افترض (بالتناقض) أن T [v]> d (s، v) ، أي المسار الذي تم العثور عليه يؤدي من سالخامس الخامس،ليس الأقصر. ثم يجب أن يكون هناك رؤوس غير مميزة على طول هذا المسار. تأمل القمة الأولى ثعلى هذا الطريق بحيث [ث] = 0. لدينا: T [w] = د (ث ، ث) ⩽ د (ق> ت)< Т[v],что противоречит выбору вершины u.
تعقيد الوقت
يعتمد تعقيد خوارزمية Dijkstra على طريقة العثور على الرأس غير المرئي مع الحد الأدنى من المسافة إلى الرأس الأصلي ، وطريقة تخزين مجموعة الرؤوس غير المرئية ، وطريقة تحديث الملصقات. لنفترض أن n هو عدد الرؤوس ، وبعد m - عدد الأضلاع في الرسم البياني. ثم ، في أبسط الحالات ، عندما يتم النظر إلى مجموعة الرؤوس بأكملها للبحث عن قمة ذات مسافة دنيا عن القمة الأولية ، ويتم استخدام مصفوفة لتخزين المسافات ، يكون وقت تشغيل الخوارزمية هو O (n 2). يتم تنفيذ الحلقة الرئيسية حوالي n مرة ، في كل منها يتم إنفاق حوالي n من العمليات للعثور على الحد الأدنى. يتم إنفاق عدد العمليات المتناسبة مع عدد الحواف m (نظرًا لأن كل حافة تحدث مرتين بالضبط في هذه الدورات وتتطلب عددًا ثابتًا من العمليات) يتم إنفاقها على حلقات على طول جيران كل قمة تمت زيارتها. وبالتالي ، فإن إجمالي وقت تشغيل الخوارزمية هو O (n 2 + m) ، ولكن نظرًا لأن m أقل بكثير من n (n-1) ، في النهاية نحصل على O (n 2).
بالنسبة إلى الرسوم البيانية المتفرقة (أي تلك التي تكون m أقل بكثير من n²) ، يمكن تخزين الرؤوس غير المرئية في الكومة الثنائية ، ويمكن استخدام قيم المسافة كمفتاح. نظرًا لأن الدورة يتم تنفيذها بترتيب n مرة ، وأن عدد فترات الاسترخاء (تغييرات الملصقات) لا يزيد عن m ، فإن وقت التشغيل لهذا التنفيذ هو O (nlogn + mlogn)
مثال
حساب المسافات من الرأس 1 برؤوس يمكن اجتيازها:
يعتبر أقصر مسار باستخدام كائن رياضي يسمى الرسم البياني. بحث أقصر الطرقبين رأسين معينين في الرسم البياني. والنتيجة هي مسار ، أي سلسلة من الرؤوس والحواف تقع على رأسين متجاورين ، وطولها.
النظر في الثلاثة أكثر خوارزمية فعالةالعثور على أقصر الطرق:
- خوارزمية ديكسترا;
- خوارزمية فلويد
- خوارزميات العد.
يتم تنفيذ الخوارزميات المشار إليها بسهولة باستخدام عدد صغير من الرؤوس في الرسم البياني. مع زيادة عددهم ، مهمة البحث أقصر الطرقتصبح معقدة.
خوارزمية ديكسترا
هذه الخوارزمية عبارة عن خوارزمية على الرسوم البيانية ، اخترعها العالم الهولندي إي.ديجكستروي في عام 1959. تجد الخوارزمية أقصر مسافة من أحد رؤوس الرسم البياني إلى جميع الرؤوس الأخرى وتعمل فقط مع الرسوم البيانية التي ليس لها حواف ذات وزن سالب.
يتم تعيين وزن لكل رأس - وهذا هو وزن المسار من الرأس الأولي إلى الرأس المحدد. أيضا ، يمكن تحديد كل قمة. إذا تم تحديد الرأس ، فسيكون المسار منه إلى الرأس الأولي هو الأقصر ، إن لم يكن كذلك ، فهو مؤقت. عبر الرسم البياني ، تحسب الخوارزمية مسارًا لكل رأس ، وإذا اتضح أنها الأقصر ، تحدد قمة. وزن هذا الرأس يصبح وزن المسار. بالنسبة لجميع جيران رأس معين ، تحسب الخوارزمية أيضًا الوزن ، مع عدم إبرازهم تحت أي ظرف من الظروف. تنتهي الخوارزمية من عملها ، وتصل إلى الذروة النهائية ، وتزن أقصر الطرقيصبح وزن الرأس النهائي.
خوارزمية ديكسترا
الخطوة 1. يتم تعيين وزن لجميع الرؤوس ، باستثناء الرأس الأول ، يساوي ما لا نهاية ، والرأس الأول - 0.
الخطوة 2. لم يتم تحديد جميع القمم.
الخطوة 3. يتم الإعلان عن الذروة الأولى الحالية.
الخطوة 4. يتم إعادة حساب وزن جميع الرؤوس غير المحددة وفقًا للصيغة: وزن الرأس غير المحدد هو الحد الأدنى من الوزن القديم لهذا الرأس ، ومجموع وزن الرأس الحالي ، ووزن الحافة ربط الرأس الحالي بالرأس غير المختار.
الخطوة 5. من بين القمم غير المختارة ، يتم البحث عن الرأس ذي الوزن الأدنى. إذا لم يتم العثور على واحد ، أي أن وزن جميع الرؤوس يساوي اللانهاية ، فإن المسار غير موجود. ومن هنا المخرج. خلاف ذلك ، يصبح الرأس الموجود هو الرأس الحالي. هي تبرز.
الخطوة 6. إذا كان الرأس الحالي هو الأخير ، فسيتم إيجاد المسار ، ووزنه هو وزن الرأس الأخير.
الخطوة 7. انتقل إلى الخطوة 4.
في تنفيذ البرامج خوارزمية ديكسترانقوم ببناء مجموعة S من القمم التي تعرف بالفعل أقصر المسارات من القمة الأولية. في كل خطوة ، تتم إضافة أحد الرؤوس المتبقية إلى المجموعة S ، والمسافة التي تكون المسافة من الرأس الأولي أقل من المسافة بين الرؤوس الأخرى المتبقية. في هذه الحالة ، سنستخدم المصفوفة D ، التي كتبت فيها الأطوال أقصر الطرقلكل رأس. عندما تحتوي المجموعة S على جميع رؤوس الرسم البياني ، فإن المصفوفة D ستحتوي على الأطوال أقصر الطرقمن قمة البداية إلى كل قمة.
بالإضافة إلى هذه المصفوفات ، سنستخدم مصفوفة من أطوال C ، حيث يكون العنصر C هو طول الحافة (i ، j) ، إذا لم يكن هناك حافة ، فسيتم افتراض أن طولها يساوي اللانهاية ، أي ، أكبر من أي طول حقيقي للحواف. في الواقع ، المصفوفة C هي مصفوفة الجوار، حيث يتم استبدال جميع العناصر الصفرية بما لا نهاية.
لتحديد جدا