الگوریتم دایکسترا یک الگوریتم گرافی است که کوتاه ترین مسیر را بین دو راس داده شده در یک نمودار با طول قوس غیر منفی پیدا می کند. همچنین، وظیفه محاسبه کوتاه‌ترین مسیر از یک راس معین به همه راس‌های دیگر اغلب مطرح می‌شود. این الگوریتم به طور گسترده در برنامه نویسی استفاده می شود، به عنوان مثال، از آن توسط پروتکل های مسیریابی استفاده می شود.

شرح

ورودی الگوریتم یک نمودار جهت دار وزنی با کمان هایی با وزن غیر منفی است. خروجی مجموعه ای از کوتاه ترین مسیرها از یک راس معین به سایرین است.

در ابتدا فاصله برای راس اولیه صفر و فاصله تا بقیه را بی نهایت در نظر گرفته شده است. آرایه‌ای از پرچم‌ها که نشان می‌دهد آیا راس عبور کرده است یا خیر، با صفر پر شده است. سپس در هر مرحله از حلقه، یک راس با حداقل فاصله تا راس اولیه و یک پرچم برابر با صفر جستجو می شود. یک پرچم برای آن تنظیم شده و تمام رئوس همسایه بررسی می شوند. اگر فاصله محاسبه شده قبلی از راس منبع تا راس بررسی شده بیشتر از مجموع فاصله تا راس فعلی و طول یال از آن تا راس بررسی شده باشد، فاصله تا راس بررسی شده با فاصله برابر می شود. به فعلی + لبه از فعلی به علامت زده شده. حلقه زمانی به پایان می رسد که پرچم همه رئوس برابر با 1 شود، یا زمانی که فاصله تا همه رئوس با پرچم 0 بی نهایت باشد. مورد دوم در صورت قطع ارتباط نمودار امکان پذیر است.

الگوریتم دایکسترا در شبه کد

ورود: از جانب: آرایه واقعی – ماتریس طول کمان های نمودار. s رأسی است که کوتاه ترین مسیر از آن جستجو می شود و t رأسی است که برای رسیدن به آن جستجو می شود.

خروجی: بردارهای T: آرایه واقعی; و H: آرایه 0..r. اگر بالا vدر کوتاه ترین مسیر از سبه تی،سپس تلویزیون]- کوتاه ترین طول مسیر از سبه y; خوب] -اوج بلافاصله قبل از دردر کوتاه ترین مسیر

H آرایه ای است که در آن راس n با راس m مطابقت دارد و راس قبلی در مسیر n از s است.

T آرایه ای است که راس n با فاصله آن تا s مطابقت دارد.

X آرایه ای است که در آن راس n با 1 مطابقت دارد اگر مسیر آن مشخص باشد و 0 در غیر این صورت.

مقداردهی اولیه آرایه:

برای vاز 1 تا آرانجام دادن

T[v]: = ∞ (میانبر ناشناخته)

X[v]: = 0 (همه راس ها بدون علامت هستند)

H[s]: = 0 ( س هیچ چیز پیش نمی آید)

T[s]:= 0 (کوتاه ترین مسیر دارای طول 0 است...)

X[s]:= 1 (...و او شناخته شده است) v : = س (بالای فعلی)

م: (به روز رسانی یادداشت ها)

برای و ∈ G( و) انجام دادن

اگر X[i] = 0 & T[u]> تلویزیون] + سیسپس

T[u]: = تلویزیون] + سی(یک مسیر کوتاهتر از س که در واز طریق v }

h[u]:= v(به خاطر بسپار)

متر: = ∞

v : = 0

(پیدا کردن انتهای کوتاه ترین مسیر)

برای واز 1 تا پ انجام دادن

اگر X[u] = 0 &T[u]< تیسپس

v:= تو;

m:= T[u]( بالا v کوتاه ترین مسیر را از س

اگر v = 0 سپس

توقف (راهی برای خروج نیست س که در تی) پایان اگر

اگر v= تیسپس

توقف (کوتاه ترین مسیر را پیدا کرد س که در تی) پایان اگر

X[v]: = 1 (کوتاه ترین مسیر را پیدا کرد س که در v ) قابل اعتماد و متخصص م

بنیاد و پایه

برای اثبات درستی الگوریتم دایکسترا، توجه به این نکته کافی است که برای هر اجرای بدنه حلقه که با برچسب M شروع می شود، به عنوان vیک راس استفاده می شود که کوتاه ترین مسیر از راس برای آن مشخص است سبه عبارت دیگر، اگر X[v] = 1، آنگاه T[v] = d(s,v) , و تمام رئوس در مسیر (s, v) تعریف شده توسط بردار H دارای ویژگی یکسانی هستند.

Vu T[u] = 1 => T[u] = d(s,u)&T] = 1.

در واقع (با استقرا)، اولین بار به عنوان vاز راس s استفاده می‌شود که کوتاه‌ترین مسیر برای آن خالی است و طول آن 0 است (مسیرهای غیر خالی نمی‌توانند کوتاه‌تر باشند، زیرا طول قوس‌ها غیرمنفی هستند). فرض کنید T[u] = d(s,u) برای همه رئوس قبلی برچسب گذاری شده است وراس جدید برچسب گذاری شده را در نظر بگیرید v، که از شرط T[v] = min T[u] انتخاب می شود. توجه داشته باشید که اگر مسیری که از رئوس برچسب گذاری شده می گذرد مشخص باشد، کوتاه ترین مسیر مشخص است. فرض کنید (برعکس) که T[v] > d(s, v)، یعنی مسیر پیدا شده منتهی به سکه در vکوتاه ترین نیست سپس باید رئوس بدون برچسب در این مسیر وجود داشته باشد. راس اول را در نظر بگیرید wدر این مسیر به طوری که T[w] = 0. ما داریم: T[w] = d(s,w)⩽d(s>v)< Т[v],что противоречит выбору вершины u.

پیچیدگی زمانی

پیچیدگی الگوریتم Dijkstra بستگی به نحوه یافتن یک راس بازدید نشده با حداقل فاصله از راس اصلی، نحوه ذخیره مجموعه رئوس بازدید نشده و نحوه به روز رسانی برچسب ها دارد. n تعداد رئوس و m تعداد یال های نمودار باشد. سپس در ساده‌ترین حالت، زمانی که کل مجموعه راس‌ها برای یافتن راس با حداقل فاصله تا راس اصلی جستجو می‌شود و از آرایه‌ای برای ذخیره فواصل استفاده می‌شود، زمان اجرای الگوریتم O(n 2) است. حلقه اصلی حدود n بار اجرا می شود، در هر یک از آنها حدود n عملیات صرف یافتن حداقل می شود. چرخش از طریق همسایگان هر رأس بازدید شده تعدادی عملیات متناسب با تعداد یال های m انجام می دهد (زیرا هر یال دقیقاً دو بار در این چرخه ها اتفاق می افتد و به تعداد عملیات ثابت نیاز دارد). بنابراین، کل زمان اجرای الگوریتم O(n 2 +m) است، اما از آنجایی که m بسیار کمتر از n(n-1) است، در نهایت به O(n2) می رسد.

برای نمودارهای پراکنده (یعنی آنهایی که m برای آنها بسیار کمتر از n² است)، رئوس بازدید نشده را می توان در یک پشته باینری ذخیره کرد و مقادیر فاصله به عنوان یک کلید استفاده می شود. از آنجایی که حلقه حدود n بار اجرا می شود و تعداد استراحت ها (تغییر برچسب) بیشتر از m نیست، زمان اجرای چنین پیاده سازی O(nlogn+mlogn) است.

مثال

محاسبه فاصله از راس 1 توسط رئوس قابل پیمایش:

مثال یافتن کوتاه ترین مسیر را در نظر بگیرید. شبکه ای از بزرگراه ها که مناطق شهر را به هم وصل می کند داده شده است. برخی از جاده ها یک طرفه هستند. کوتاه ترین مسیرها را از مرکز شهر تا هر شهر در منطقه پیدا کنید.

برای حل این مشکل می توانید استفاده کنید الگوریتم دایکسترا- الگوریتمی بر روی نمودارها که توسط دانشمند هلندی E. Dijkstra در سال 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
#عبارتند از
#عبارتند از
#SIZE 6 را تعریف کنید
int main()
{
int a; // ماتریس اتصالات
int d; // حداقل فاصله
در تلویزیون؛ // رئوس بازدید شده
int temp, miniindex, min;
int begin_index = 0;
system("chcp 1251");
system("cls");
// اولیه سازی ماتریس رابطه
برای (int i = 0; i {
a[i][i] = 0;
برای (int j = i + 1; j printf( "فاصله %d - %d را وارد کنید:", i + 1, j + 1);
scanf("%d" , &temp);
a[i][j] = دما;
a[j][i] = دما;
}
}
// نمایش ماتریس رابطه
برای (int i = 0; i {
برای (int j = 0; j printf("%5d " , a[i][j]);
printf("\n");
}
//راس ها و فواصل را راه اندازی کنید
برای (int i = 0; i {
d[i] = 10000;
v[i] = 1;
}
d=0;
// مرحله الگوریتم
انجام دادن(
حداقل شاخص = 10000;
حداقل = 10000;
برای (int i = 0; i { // اگر راس هنوز بازدید نشده باشد و وزن آن کمتر از min باشد
اگر ((v[i] == 1) && (d[i] { // تخصیص مجدد مقادیر
min = d[i];
miniindex=i;
}
}
// حداقل وزن پیدا شده را اضافه کنید
// به وزن راس فعلی
// و با حداقل وزن راس فعلی مقایسه کنید
اگر (minindex != 10000)
{
برای (int i = 0; i {
اگر (a[i] > 0)
{
temp = min + a[i];
اگر (دمای< d[i])
{
d[i] = دما;
}
}
}
v = 0;
}
) در حالی که (minindex< 10000);
// نمایش کوتاه ترین فواصل تا رئوس
printf( "\nکوتاهترین فاصله تا رئوس: \n");
برای (int i = 0; i printf("%5d " , d[i]);

// بازیابی مسیر
درونی؛ // آرایه از رئوس بازدید شده
int end = 4; // شاخص راس انتهایی = 5 - 1
ver = پایان + 1; // عنصر شروع - راس پایان
int k = 1; // شاخص پیک قبلی
وزن int = d; // وزن راس انتهایی

در حالی که (پایان != begin_index) // تا زمانی که به راس شروع برسیم
{
برای (int i = 0; i // به همه رئوس نگاه کنید
اگر (a[i] != 0) // اگر ارتباطی وجود دارد
{
int temp = وزن - a[i]; // وزن مسیر را از راس قبلی تعیین کنید
اگر (دمای == d[i]) // اگر وزن با وزن محاسبه شده مطابقت داشته باشد
{ // یعنی انتقالی از این رأس وجود داشته است
وزن = دما // وزن جدید را ذخیره کنید
پایان = من // راس قبلی را ذخیره کنید
ver[k] = i + 1; // و آن را در یک آرایه بنویسید
k++;
}
}
}
// نمایش مسیر (راس شروع در انتهای آرایه k عناصر است)
printf( "\nخروجی کوتاهترین مسیر\n");
برای (int i = k - 1; i >= 0; i--)
printf("%3d " , ver[i]);
getchar(); getchar();
بازگشت 0;
}

نتیجه اجرا


بازگشت:

یک نمودار وزن دار جهت دار یا غیر جهت دار با رئوس و یال ها داده می شود. وزن تمام لبه ها غیر منفی است. مقداری راس شروع مشخص شده است. لازم است طول کوتاه‌ترین مسیرها از یک راس تا همه راس‌های دیگر را پیدا کنید و همچنین راهی برای خروجی کوتاه‌ترین مسیرها از خود ارائه کنید.

این مشکل کوتاهترین مسیرهای تک منبعی نامیده می شود.

الگوریتم

این الگوریتم ارائه شده توسط محقق هلندی را توصیف می کند دایکسترا(Dijkstra) در سال 1959

بیایید آرایه ای بگیریم که در آن برای هر رأس، طول فعلی کوتاه ترین مسیر از تا را ذخیره می کنیم. در ابتدا و برای همه رئوس دیگر، این طول برابر با بی‌نهایت است (زمانی که در رایانه پیاده‌سازی می‌شود، معمولاً تعداد به اندازه کافی بزرگ به‌عنوان بی‌نهایت انتخاب می‌شود که آشکارا بیشتر از طول مسیر ممکن است):

علاوه بر این، برای هر رأس ذخیره می کنیم که آیا هنوز برچسب زده شده است یا نه، یعنی. بیایید یک آرایه بولی بگیریم. در ابتدا، همه رئوس بدون برچسب هستند، یعنی.

خود الگوریتم دایکسترا شامل تکرارها. در تکرار بعدی، راس با کمترین مقدار در بین مواردی که هنوز برچسب گذاری نشده اند انتخاب می شود، یعنی:

(مشخص است که در اولین تکرار، راس شروع انتخاب خواهد شد.)

راس انتخاب شده به این صورت علامت گذاری شده است. علاوه بر این، در تکرار فعلی، از راس، آرامش: تمام یال های خروجی از راس از طریق بررسی می شوند و برای هر یک از این رئوس الگوریتم سعی می کند مقدار . بگذارید طول لبه فعلی باشد، سپس در قالب یک کد، آرامش به نظر می رسد:

اینجا جایی است که تکرار فعلی به پایان می رسد، الگوریتم به تکرار بعدی ادامه می دهد (دوباره، راس با کوچکترین مقدار انتخاب می شود، آرامش ها از آن انجام می شود و غیره). در این حالت در نهایت پس از تکرارها، تمام رئوس نمودار برچسب گذاری می شوند و الگوریتم کار خود را کامل می کند. ادعا می شود که مقادیر یافت شده طول های مورد نیاز کوتاه ترین مسیرها از تا هستند.

شایان ذکر است که اگر همه رئوس نمودار از راس قابل دسترسی نباشند، مقادیر برای آنها بی نهایت باقی خواهد ماند. واضح است که چند تکرار آخر الگوریتم فقط این رئوس را انتخاب می کند، اما این تکرارها هیچ کار مفیدی ایجاد نمی کنند (زیرا یک فاصله نامتناهی نمی تواند سایر فواصل، حتی بی نهایت) را کاهش دهد. بنابراین، به محض اینکه یک راس با فاصله بی نهایت به عنوان راس انتخاب شده در نظر گرفته شود، می توان بلافاصله الگوریتم را متوقف کرد.

ترمیم مسیر. البته معمولاً نه تنها طول کوتاه ترین مسیرها، بلکه خود مسیرها را نیز باید دانست. اجازه دهید نحوه ذخیره اطلاعات کافی برای بازسازی بعدی کوتاهترین مسیر از هر راس را نشان دهیم. برای این، به اصطلاح آرایه اجدادی: آرایه ای که برای هر راس، تعداد راس ماقبل آخر را در کوتاه ترین مسیر به راس نگه می دارد. این از این واقعیت استفاده می‌کند که اگر کوتاه‌ترین مسیر را به یک راس انتخاب کنیم، و سپس آخرین راس را از این مسیر حذف کنیم، مسیری به دست می‌آید که به یک راس ختم می‌شود، و این مسیر برای راس کوتاه‌ترین خواهد بود. بنابراین، اگر ما این آرایه از اجداد را داشته باشیم، می‌توان کوتاه‌ترین مسیر را از آن بازیابی کرد، به سادگی هر بار جد را از راس فعلی گرفته تا به راس شروع برسیم - به این ترتیب کوتاه‌ترین مسیر مورد نظر را به دست می‌آوریم، اما در نوشته شده در به صورت برعکس. بنابراین کوتاه ترین مسیر برای رسیدن به قله این است:

باید بدانیم که چگونه این آرایه از اجداد را بسازیم. با این حال، این کار بسیار ساده انجام می شود: با هر آرامش موفقیت آمیز، یعنی. هنگامی که از راس انتخاب شده بهبودی در فاصله تا یک راس وجود دارد، می نویسیم که جد راس همان راس است:

اثبات

بیانیه اصلی، که درستی الگوریتم دایکسترا بر اساس آن استوار است به شرح زیر است. بیان شده است که پس از علامت گذاری هر راس، فاصله فعلی تا آن از قبل کمتر است و بر این اساس، دیگر تغییر نخواهد کرد.

اثباتما با القاء تولید خواهیم کرد. برای تکرار اول، اعتبار آن واضح است - برای راس ما، که طول کوتاه ترین مسیر به آن است. حال اجازه دهید این ادعا برای همه تکرارهای قبلی، یعنی. همه رئوس از قبل علامت گذاری شده اند. اجازه دهید ثابت کنیم که پس از اجرای تکرار فعلی نقض نشده است. بگذارید راس انتخاب شده در تکرار فعلی باشد، یعنی. راسی که الگوریتم قرار است برچسب گذاری کند. اجازه دهید ثابت کنیم که واقعاً برابر است با طول کوتاه ترین مسیر به آن (این طول را با نشان می دهیم).

کوتاه ترین مسیر به سمت بالا را در نظر بگیرید. واضح است که این مسیر را می توان به دو مسیر تقسیم کرد: فقط از رئوس مشخص شده (حداقل راس شروع در این مسیر خواهد بود) و بقیه مسیر (می تواند شامل رئوس علامت گذاری شده نیز باشد، اما همیشه شروع می شود) با یکی بدون علامت). با راس اول مسیر و با راس آخر مسیر مشخص کنید.

اجازه دهید ابتدا ادعای خود را برای راس ثابت کنیم، یعنی: بیایید برابری را ثابت کنیم با این حال، این تقریباً واضح است: از این گذشته، در یکی از تکرارهای قبلی، ما یک راس را انتخاب کردیم و از آن آرامش را انجام دادیم. از آنجایی که (به دلیل انتخاب رأس ) کوتاهترین مسیر به مساوی است با کوتاهترین مسیر به اضافه لبه، پس هنگامی که شل کردن از انجام می شود، مقدار در واقع به مقدار لازم تنظیم می شود.

به دلیل منفی نبودن هزینه‌های لبه‌ها، طول کوتاه‌ترین مسیر (که طبق آنچه اخیراً ثابت شد برابر است با ) از طول کوتاه‌ترین مسیر تا راس تجاوز نمی‌کند. با توجه به این که (به هر حال، الگوریتم دایکسترا نتوانست مسیری کوتاه‌تر از حد معمول پیدا کند)، در نتیجه، روابط زیر را به دست می‌آوریم:

از طرف دیگر، از آنجایی که هر دو و و رئوس بدون برچسب هستند، از آنجایی که این راس بود که در تکرار فعلی انتخاب شد و نه راس، نابرابری دیگری به دست می‌آوریم:

از این دو نابرابری، برابری را نتیجه می گیریم و سپس از روابطی که قبلاً یافت شد، به دست می آوریم و:

Q.E.D.

پیاده سازی

بنابراین، الگوریتم Dijkstra شامل تکرارهایی است که در هر یک از آنها یک راس بدون برچسب با کوچکترین مقدار انتخاب می شود، این راس برچسب گذاری می شود و سپس تمام یال های خروجی از این راس بررسی می شوند و در امتداد هر یال تلاش برای بهبود مقدار در انتهای دیگر لبه.

زمان اجرای الگوریتم حاصل جمع موارد زیر است:

با ساده ترین اجرای این عملیات، عملیات برای یافتن یک راس و عملیات روی یک آرامش و نهایی صرف می شود. مجانبیالگوریتم این است:

پیاده سازی:

const int INF = 1000000000 ; int main() ( int n؛ ... خواندن n ... بردار< vector < pair< int ,int >> > g(n); ... خواندن نمودار ... int s = ...; // راس شروعبردار< int >d(n، INF)، p(n) ; d[s] = 0; بردار< char >u(n); برای (int i= 0 ; i< n; ++ i) { int v = - 1 ; for (int j= 0 ; j< n; ++ j) if (! u[ j] && (v == - 1 || d[ j] < d[ v] ) ) v = j; if (d[ v] == INF) break ; u[ v] = true ; for (size_t j= 0 ; j< g[ v] .size () ; ++ j) { int to = g[ v] [ j] .first , len = g[ v] [ j] .second ; if (d[ v] + len < d[ to] ) { d[ to] = d[ v] + len; p[ to] = v; } } } }

در اینجا نمودار به شکل لیست های مجاورت ذخیره می شود: برای هر رأس، لیست حاوی لیستی از یال های ناشی از این راس است، به عنوان مثال. فهرستی از جفت‌ها >، که در آن اولین عنصر جفت، رأسی است که لبه به آن منتهی می‌شود، و عنصر دوم وزن یال است.

5.4.3. مسئله کوتاه ترین مسیر و الگوریتم دایکسترا برای حل آن

اجازه دهید نمودار داده شود جی(V, E) که به هر کمان عددی اختصاص داده شده است
تماس گرفت طول کمان.

تعریف. طولمسیر مجموع طول کمان هایی است که این مسیر را تشکیل می دهند. مشکل کوتاه ترین مسیراینجوری بذار

انتخاب 1.طول کوتاه ترین مسیرها (مسیرهایی با حداقل طول) و خود مسیرها را از یک راس ثابت بیابید. سبه تمام رئوس دیگر نمودار.

گزینه 2.طول کوتاه ترین مسیرها و خود مسیرها را بین تمام جفت رئوس در نمودار داده شده پیدا کنید.

اگر نمودار دارای کمان هایی با طول منفی باشد، مشکل ممکن است راه حل نداشته باشد (معنای خود را از دست خواهد داد). این به دلیل این واقعیت است که نمودار ممکن است دارای یک خط با طول منفی باشد. وجود خطوط با طول منفی به این معنی است که طول مسیر را می توان برابر با
. و اگر خطوط طول منفی وجود نداشته باشد، کوتاه ترین مسیرها وجود دارد و هر کوتاه ترین مسیر یک زنجیره ساده است.

توجه داشته باشید که اگر کوتاهترین مسیر وجود داشته باشد، هر یک از مسیرهای فرعی آن نیز کوتاهترین مسیر بین رئوس مربوطه است.

الگوریتم دایکسترا برای حل مسئله کوتاهترین مسیر.

این الگوریتم با کمان هایی با طول مثبت کار می کند و کوتاه ترین مسیرها را از یک راس ثابت تعیین می کند. سبه تمام رئوس دیگر نمودار. بیایید این رئوس را برچسب گذاری کنیم v 1 , v 2 ,…, v n .

تعریف.بیایید راس را صدا کنیم تودراز کشیدن نزدیک تر به بالا ساز بالا vاگر طول کوتاه ترین مسیر از سقبل از توکمتر از طول کوتاه ترین مسیر از سقبل از v. خواهیم گفت که قله ها توو v مساوی فاصلهاز بالا س، اگر طول کوتاه ترین مسیرها از سقبل از توو از سقبل از vهمخوانی داشتن.

الگوریتم دایکسترا به صورت متوالی رئوس یک گراف را بر حسب مجاورت با راس مرتب می کند. سو بر اساس اصول اساسی زیر است.

اگر طول قوس اعداد مثبت باشد، پس

نزدیکترین به س بالا خودش است طول کوتاه ترین مسیر از سقبل از س 0 است؛

نزدیکترین به س راس غیر از س، دروغ از سدر فاصله یک کمان - کوتاهترین کمان از راس خارج شده است س;

هر رأس میانی کوتاه ترین مسیر از ستا یک قله vنزدیک تر است ساز راس انتهایی v;

کوتاه ترین مسیر به راس مرتب بعدی فقط می تواند از رئوس از قبل مرتب شده عبور کند.

بگذارید الگوریتم قبلاً رئوس را مرتب کرده باشد v 1 , v 2 … v ک . با نشان دادن
,
طول کوتاه ترین مسیر به سمت بالا v من .

تمام کمان های نمودار اصلی را در نظر بگیرید که از یکی از رئوس مجموعه شروع می شوند
و در رئوس هنوز نامرتب خاتمه می یابد. برای هر یک از این قوس ها، برای مثال
، جمع را محاسبه کنید
. این مجموع برابر است با طول مسیر از س که در y، که در آن بالا v منرأس ماقبل آخر و مسیر از است س که در v منکوتاه ترین مسیرهای اتصال است س و v من .

این طول تمام مسیرها را تعیین می کند سبه رئوس هنوز مرتب نشده، که در آنها فقط رئوس از میان رئوس میانی هستند کنزدیکترین به س. بگذارید کوتاه ترین این مسیرها به بالا ختم شود w. سپس wو بخور
نزدیک به سراس

از نظر فنی، اقدامات مطابق با الگوریتم Dijkstra با استفاده از دستگاه برچسب های راس انجام می شود. برچسب رأس vبه عنوان نشان داده شده است
. هر برچسب عددی برابر با طول مسیری از آن است س قبل از v. برچسب ها به دو دسته موقت و دائمی تقسیم می شوند. در هر مرحله فقط یک برچسب دائمی می شود. یعنی مقدار آن برابر با طول کوتاه ترین مسیر به راس مربوطه است و خود این راس مرتب شده است. تعداد راس مرتب بعدی با حرف نشان داده می شود آر.

شرح الگوریتم.

مرحله 1. (تنظیمات اولیه). قرار دادن
و این برچسب را دائمی در نظر بگیرید. قرار دادن
,
و این برچسب ها را موقتی در نظر بگیرید. قرار دادن
.

گام 2 (مرحله عمومی).تکرار می شود n بارها تا زمانی که تمام رئوس نمودار مرتب شوند.

مهر زمانی را دوباره محاسبه کنید
هر راس نامرتب v من، که شامل قوس خروج از رأس است R،طبق قاعده

راس را با حداقل مهر زمانی انتخاب کنید. اگر چندین رئوس وجود دارد، یکی را انتخاب کنید.

اجازه دهید w- راس با حداقل مهر زمانی علامت را بخوانید
ثابت و قرار داده شود
.

به راحتی می توان مراحل الگوریتم Dijkstra را در یک جدول مرتب کرد که هر ستون آن مربوط به یک راس نمودار است. سطرهای جدول با تکرار مرحله رایج مطابقت دارد.

مثال. برای نمودار در شکل. 4. کوتاه ترین مسیرها را از رئوس پیدا کنید
به تمام رئوس دیگر نمودار. لبه ها به معنای دو قوس متفاوت با طول یکسان است.

راه حل.روی میز. 1 برچسب از رئوس در هر مرحله نوشته می شود. علائم دائمی با علامت "+" مشخص می شوند. اجازه دهید نحوه محاسبه برچسب های راس را با جزئیات شرح دهیم.

از راس 1، کمان ها به رئوس 2، 5، 6 می روند. برچسب های این راس ها را دوباره محاسبه کرده و ردیف دوم جدول را پر کنید.

برچسب رأس 6 دائمی می شود،
.

از رأس 6، کمان ها تا رئوس هنوز نامرتب 2، 5، 8، 9 خارج می شوند. مهرهای زمانی آنها را دوباره محاسبه کنید

ردیف 3 جدول را پر کنید. حداقل مهر زمانی 3 است (برچسب راس 9)،
.

از راس 9، کمان ها به رئوس هنوز نامرتب 5، 8، 11، 12 می روند. سپس

سطر چهارم جدول را پر کنید. در این خط، دو راس - 2 و 12 دارای حداقل مهر زمانی برابر با 4 هستند. ابتدا اجازه دهید مثلاً راس 2 را مرتب کنیم. سپس در مرحله بعد، راس 12 مرتب می شود.

میز 1

بنابراین،
.

از راس 2، کمان ها به رئوس هنوز نامرتب 3، 4، 5 می روند. مهرهای زمانی این راس ها را دوباره محاسبه کنید.

ردیف 5 جدول را پر کنید. حداقل مهر زمانی 4 است (برچسب رأس 12)،
.

ردیف 6 جدول را پر کنید. حداقل مهر زمانی 5 است (برچسب راس 5)،
.

ردیف 7 جدول را پر کنید. برچسب راس 8 ثابت می شود (برابر با 5 است)
.

راس 11 سفارش داده شده است.

از راس 11، کمان ها خارج می شوند تا رئوس نامرتب 7، 10. مهرهای زمانی این راس ها را دوباره محاسبه کنید.

Vertex 4 یک برچسب دائمی می گیرد.

از راس 4، کمان ها به رئوس نامرتب 3، 7 می روند. مهرهای زمانی را دوباره محاسبه کنید

بالا 3 را مرتب کنید.

سطر 12 جدول را پر کنید. در این مرحله آخرین راس نامرتب 10 را مرتب می کنیم.

ساختن درختی از کوتاه ترین مسیرها

کوتاه ترین درخت مسیر درختی است که در یک راس ریشه دارد. اس . تمام مسیرهای این درخت کوتاه ترین مسیر برای این نمودار هستند.

کوتاه ترین درخت مسیر مطابق جدول ساخته شده است، راس به رأس به ترتیبی که برچسب های دائمی دریافت کردند در آن گنجانده شده است. ریشه اولین گره ای است که در درخت قرار می گیرد. اس .

بیایید برای مثال خود درختی از کوتاه ترین مسیرها بسازیم.

ابتدا ریشه راس 1 را در درخت قرار می دهیم سپس کمان (1،6) در درخت قرار می گیرد. در مرحله بعد راس 9 ترتیب داده شد که طول کوتاهترین مسیر برابر با 3 است. اولین بار عدد 3 در ردیف سوم ظاهر شد که با پر شده بود
. بنابراین، راس 6 ماقبل آخر راس کوتاه ترین مسیر به راس 9 است. کمان (6،9) به طول 1 را در درخت قرار می دهیم.

سپس راس 2 با کوتاه ترین طول مسیر برابر با 4 مرتب شد. این عدد ابتدا در ردیف سوم ظاهر شد که با پر شده بود.
. در نتیجه، کوتاه ترین مسیر به راس دوم از امتداد کمان می گذرد (6،2). قوس (6،2) به طول 2 را در درخت قرار می دهیم.

بعد، راس 12 مرتب شد،
. اولین بار عدد 4 در سطر چهارم ظاهر می شود که در چه زمانی پر شده است
. قوس (9،12) به طول 1 در درخت گنجانده شده است. درخت کامل کوتاهترین مسیرها در شکل نشان داده شده است. 5.

اگر نمودار دارای کمان هایی با طول منفی باشد، الگوریتم دایکسترا ممکن است شکست بخورد. بنابراین، به دنبال کوتاه ترین مسیرها از بالا باشید س =1 برای نمودار در شکل. 6، الگوریتم ابتدا گره 3، سپس گره 2 را سفارش می دهد و پایان می دهد. علاوه بر این، این کوتاه ترین مسیر به راس 3، از دیدگاه الگوریتم دایکسترا، یک کمان (1،3) به طول 3 است.

در واقع کوتاه ترین مسیر به راس 3 از کمان های (1،2) و (2،3) تشکیل شده است که طول این مسیر 5+(-3)=2 است.

به دلیل وجود یک قوس (2،3) با طول منفی -3، اصول اساسی زیر نقض شد:

نزدیکترین به س راس در فاصله دو قوس از آن قرار دارد و نه یک.

راس میانی کوتاهترین مسیر 1-2-3 (راس 2) از راس 1 (فاصله 5) دورتر از راس نهایی مسیر 3 قرار دارد.

بنابراین، وجود کمان‌هایی با طول منفی، حل کوتاه‌ترین مسیر را پیچیده می‌کند و نیاز به استفاده از الگوریتم‌های پیچیده‌تری نسبت به الگوریتم دایکسترا دارد.

از بسیاری از الگوریتم‌ها برای یافتن کوتاه‌ترین مسیرها بر روی یک نمودار، در هابره من فقط شرحی از الگوریتم فلوید-وارشال را پیدا کردم. این الگوریتم کوتاه ترین مسیرها را بین تمام رئوس نمودار و طول آنها پیدا می کند. در این مقاله، اصل کار الگوریتم دایکسترا را شرح خواهم داد که مسیرهای بهینه و طول آنها را بین یک راس خاص (منبع) و همه رئوس دیگر نمودار پیدا می کند. نقطه ضعف این الگوریتم این است که اگر نمودار دارای قوس هایی با وزن منفی باشد، به درستی کار نمی کند.

به عنوان مثال، نمودار جهت دار G زیر را در نظر بگیرید:

ما می توانیم این نمودار را به عنوان یک ماتریس C نشان دهیم:

بیایید راس 1 را به عنوان منبع در نظر بگیریم یعنی به دنبال کوتاه ترین مسیرها از راس 1 تا رئوس 2، 3، 4 و 5 خواهیم بود.
این الگوریتم گام به گام در تمام رئوس نمودار تکرار می شود و برچسب هایی را به آنها اختصاص می دهد که حداقل فاصله شناخته شده از راس منبع تا یک راس خاص است. بیایید این الگوریتم را با یک مثال در نظر بگیریم.

بیایید یک برچسب برابر با 0 به راس 1 اختصاص دهیم، زیرا این راس منبع است. به رئوس باقی مانده برچسب هایی برابر با بی نهایت اختصاص داده می شود.

در مرحله بعد، یک راس W را انتخاب می کنیم که دارای حداقل برچسب است (حالا راس 1 است) و همه راس هایی را که از راس W مسیری وجود دارد که شامل رئوس میانجی نیست، در نظر می گیریم. به هر یک از رئوس در نظر گرفته شده یک برچسب برابر با مجموع برچسب W و طول مسیرهای W تا راس مورد نظر اختصاص می دهیم، اما تنها در صورتی که مجموع حاصل از مقدار قبلی برچسب کمتر باشد. اگر مقدار کمتر نباشد، برچسب قبلی را بدون تغییر می گذاریم.

بعد از اینکه تمام رئوس هایی را که مسیر مستقیمی از W به آنها وجود دارد در نظر گرفتیم، راس W را به عنوان بازدید شده علامت گذاری می کنیم و از بین رئوس هایی که هنوز بازدید نشده اند، رئوسی را انتخاب می کنیم که حداقل مقدار برچسب را دارد، راس بعدی W خواهد بود. در این حالت، این راس 2 یا 5 است. اگر چندین راس با برچسب های یکسان وجود داشته باشد، مهم نیست که کدام را به عنوان W انتخاب کنیم.

ما راس 2 را انتخاب می کنیم. اما هیچ مسیر خروجی از آن وجود ندارد، بنابراین بلافاصله این راس را به عنوان بازدید شده علامت گذاری می کنیم و با حداقل برچسب به راس بعدی می رویم. این بار فقط راس 5 دارای حداقل برچسب است. تمام رئوسی را در نظر بگیرید که مسیرهای مستقیم از 5 به آنها وجود دارد، اما هنوز به عنوان بازدید شده علامت گذاری نشده اند. مجدداً مجموع برچسب راس W و وزن یال را از W به راس فعلی می‌یابیم و اگر این مجموع از برچسب قبلی کمتر باشد، مقدار برچسب را با جمع حاصل جایگزین می‌کنیم.

بر اساس تصویر می بینیم که برچسب های رئوس 3 و 4 کوچکتر شده اند، یعنی مسیر کوتاه تری به این رئوس از راس مبدا پیدا شده است. بعد، راس پنجم را به عنوان بازدید شده علامت بزنید و راس بعدی را که دارای حداقل برچسب است انتخاب کنید. تا زمانی که رئوس بازدید نشده وجود داشته باشد، تمام اقدامات فوق را تکرار می کنیم.

پس از انجام تمام مراحل به نتیجه زیر می رسیم:

بردار P نیز وجود دارد که بر اساس آن می توانید کوتاه ترین مسیرها را بسازید. با تعداد عناصر این بردار برابر با تعداد رئوس نمودار است.هر عنصر حاوی آخرین راس میانی در کوتاهترین مسیر بین راس مبدا و راس نهایی است. در ابتدای الگوریتم، تمام عناصر بردار P برابر با راس منبع هستند (در مورد ما، P = (1، 1، 1، 1، 1)). علاوه بر این، در مرحله محاسبه مجدد مقدار برچسب برای راس در نظر گرفته شده، اگر برچسب راس در نظر گرفته شده به راس کوچکتر تغییر کند، مقدار راس فعلی W را در آرایه P می نویسیم. به عنوان مثال: راس 3 دارای یک برچسب با مقدار "30"، با W=1. علاوه بر این، در W=5، برچسب راس سوم به "20" تغییر کرده است، بنابراین مقدار را در بردار P - P=5 می نویسیم. همچنین، در W=5، مقدار برچسب در راس 4 تغییر کرده است ("50" بود، "40" شد)، بنابراین باید مقدار W - P=5 را به عنصر چهارم نسبت دهید. بردار P. در نتیجه، بردار Р = (1، 1، 5، 5، 1) را دریافت می کنیم.

با دانستن اینکه هر عنصر بردار P حاوی آخرین راس میانی در مسیر بین منبع و راس نهایی است، می‌توانیم خود کوتاه‌ترین مسیر را بدست آوریم.