Internet va axborot kommunikatsiyasi fakulteti

To'rtinchi qadam

Beshinchi qadam

Oltinchi qadam

Shunday qilib, 1-cho'qqidan 5-cho'qqigacha bo'lgan eng qisqa yo'l cho'qqilar orqali o'tadigan yo'l bo'ladi 1 — 3 — 6 — 5 chunki bu yo'l bilan biz 20 minimal vaznga ega bo'lamiz.
Keling, eng qisqa yo'lning hosilasini ko'rib chiqaylik. Biz har bir cho'qqi uchun yo'lning uzunligini bilamiz va endi biz uchlarini oxiridan boshlab ko'rib chiqamiz. Yakuniy cho'qqini ko'rib chiqing (bu holda, cho'qqi 5 ) va u bogʻlangan barcha choʻqqilar uchun oxirgi choʻqqining yoʻl uzunligidan mos keladigan chetning ogʻirligini ayirib, yoʻl uzunligini topamiz.
Shunday qilib, yuqori 5 yo'l uzunligi bor 20 ... U cho'qqilarga bog'langan 6 va 4 .
Yuqori uchun 6 vaznni oling 20 - 9 = 11 (mos keladi).
Yuqori uchun 4 vaznni oling 20 - 6 = 14 (mos kelmadi).
Agar natijada biz ko'rib chiqilayotgan cho'qqining yo'l uzunligiga to'g'ri keladigan qiymatni olsak (bu holda, cho'qqi 6 ), keyin aynan shu nuqtadan yakuniy cho'qqiga o'tish amalga oshirildi. Biz bu cho'qqini kerakli yo'lda belgilaymiz.
Keyinchalik, biz cho'qqiga chiqadigan chetni aniqlaymiz 6 ... Va shunga o'xshash, biz boshiga yetguncha.
Agar bunday o'tish natijasida bir necha bosqichda biz bir nechta cho'qqilar uchun bir xil qiymatlarga ega bo'lsak, biz ulardan istalganini olishimiz mumkin - bir nechta yo'llar bir xil uzunlikka ega bo'ladi.


Dijkstra algoritmini amalga oshirish
Grafik og'irliklarini saqlash uchun kvadrat matritsa ishlatiladi. Qator va ustunlar sarlavhalari grafikning uchlarini o'z ichiga oladi. Grafik yoylarining og'irliklari esa jadvalning ichki kataklariga joylashtirilgan. Grafikda halqalar mavjud emas, shuning uchun matritsaning asosiy diagonali nol qiymatlarni o'z ichiga oladi.

C ++ dasturini amalga oshirish
#aniqlang _CRT_XAVFSIZ_OGOHLANTIRISH
#o'z ichiga oladi
#o'z ichiga oladi
#6 oʻlchamini aniqlang
int main ()
{
int a; // havolalar matritsasi
int d; // minimal masofa
int v; // tashrif buyurilgan cho'qqilar
int temp, minindex, min;
int begin_index = 0;
tizim ("chcp 1251");
tizim ("cls");
// Havolalar matritsasini ishga tushiring
uchun (int i = 0; i 
{
a [i] [i] = 0;
uchun (int j = i + 1; j 
printf ( "Masofani kiriting% d -% d:", i + 1, j + 1);
scanf ("% d", & temp);
a [i] [j] = temp;
a [j] [i] = temp;
}
}
// Havolalar matritsasini ko'rsatish
uchun (int i = 0; i 
{
uchun (int j = 0; j 
printf ("% 5d", a [i] [j]);
printf ("\ n");
}
// Cho'qqilar va masofalarni ishga tushiring
uchun (int i = 0; i 
{
d [i] = 10000;
v [i] = 1;
}
d = 0;
// Algoritm bosqichi
qilmoq (
minindex = 10000;
min = 10000;
uchun (int i = 0; i 
{ // Agar cho'qqi hali yurilmagan bo'lsa va og'irlik mindan kam bo'lsa
agar ((v [i] == 1) && (d [i] { // Qiymatlarni qayta tayinlash
min = d [i];
minindex = i;
}
}
// Topilgan minimal vaznni qo'shing
// cho'qqining joriy og'irligiga
// va cho'qqining joriy minimal og'irligi bilan solishtiring
agar (minindex! = 10000)
{
uchun (int i = 0; i 
{
agar (a [i]> 0)
{
temp = min + a [i];
agar (harorat< d[i])
{
d [i] = harorat;
}
}
}
v = 0;
}
) while (minindex< 10000);
// Cho'qqilargacha bo'lgan eng qisqa masofalarni ko'rsatish
printf ( "\ nToʻqqilarga eng qisqa masofalar: \ n");
uchun (int i = 0; i 
printf ("% 5d", d [i]);

// Yo'lni tiklang

int ver; // tashrif buyurilgan cho'qqilar massivi
int end = 4; // yakuniy cho'qqi indeksi = 5 - 1
ver = end + 1; // boshlang'ich element - tugatish cho'qqisi
int k = 1; // oldingi uchining indeksi
int og'irligi = d; // oxirgi uchining og'irligi
esa (oxiri! = start_index) // hali boshlang'ich cho'qqiga etib bormagan
{
uchun (int i = 0; i // barcha cho'qqilardan o'ting
agar (a [i]! = 0) // agar ulanish mavjud bo'lsa
{
int temp = og'irlik - a [i]; // oldingi cho'qqidan yo'lning og'irligini aniqlang
agar (harorat == d [i]) // agar vazn hisoblanganga to'g'ri kelsa
{ // bu cho'qqidan o'tish sodir bo'lganligini bildiradi
vazn = harorat; // yangi vaznni saqlang
oxiri = i; // oldingi uchini saqlang
ver [k] = i + 1; // va uni massivga yozing
k ++;
}
}
}
// Yo'lni chiqaring (boshlang'ich uchi k elementli massivning oxirida edi)
printf ( "\ nEng qisqa yo'lni ko'rsatish \ n");
uchun (int i = k - 1; i> = 0; i--)
printf ("% 3d", versiya [i]);
getchar (); getchar ();
qaytish 0;
}


Amalga oshirish natijasi

Orqaga:
Dijkstra algoritmi yo'naltirilmagan grafikdagi cho'qqilar orasidagi eng qisqa yo'lni topishga mo'ljallangan.
Algoritmning g'oyasi quyidagicha: birinchi navbatda, nolga teng bo'lgan boshlang'ich cho'qqigacha bo'lgan yo'lni tanlaymiz va bu cho'qqini allaqachon tanlanganlar to'plamiga qo'shamiz, qolgan tanlanmagan cho'qqilargacha bo'lgan masofa aniqlanadi. Har bir keyingi bosqichda biz keyingi tanlangan cho'qqini topamiz, uning masofasi eng kichik va tanlanmaganlar to'plamidan biron bir cho'qqiga chekka bilan bog'langan (bu masofa tanlangan cho'qqigacha bo'lgan masofaga va uzunligiga teng bo'ladi). chetidan).