Algoritmdan nazorat savollariga javoblar Algoritm nima

Grafdagi eng qisqa yo’l topish. Grafda yo’l bu – bir uchdan boshqa uchga boradigan uchlar va qirralar ketma-ketligiga aytiladi. Qirralar soni esa yo’l uzunligi deb ataladi. Eng qisqa yo’l qirralar soni eng kichik bo’ladiga yo’lga aytiladi. Chuqurlik bo’yicha izlash algoritmi aynan qirralar soni bo’ticha eng qisqa yo’lni topadi. Bunig uchun qo’shimcha d[] massivini kiritamiz. Dastlabki uch uchun d[v] = 0. Navbatdan olingan har bir v uchni oladigan bo’lsak, unga qo’shni bo’lgan hali ko’rilmagan u uchga yana bitta qirra orqali o’tib borish kerak. Shuning uchun d[u] = d[v]+1 qilib belgilab qo’yamiz.

Yuqoridagi graf uchun eng qisqa masofalar quyidagicha bo’ladi: