# Working with Dijkstra's algorithm

Keling, ushbu grafik bilan qanday ishlashini ko'rib chiqaylik.

![graph](/files/A3OfIlVXPCtrXzH9cQbA)

Har bir segmentda bir necha daqiqada sayohat vaqti bor. Eng qisqa vaqt ichida boshidan oxirigacha borish uchun siz Dijkstra algoritmidan foydalanasiz.

Agar siz ushbu grafikda birinchi bo'lib qidiruvni amalga oshirsangiz, eng qisqa yo'lni olasiz.

![fastest way](/files/LFRZWaoRDYKCmE4RI9MX)

Ammo bu yo'l 7 daqiqa davom etadi. Keling, ko'rib chiqaylik, siz kamroq vaqt talab qiladigan yo'lni topa olasizmi? Dijkstra algoritmiga to'rtta qadam bor:

1. "Eng arzon" tugunni toping. Bu siz eng kam vaqt ichida kirishingiz mumkin bo'lgan tugun.
2. Ushbu tugunning qo'shnilarining xarajatlarini yangilang. Bu bilan nimani nazarda tutayotganimni tez orada tushuntiraman.
3. Grafikdagi har bir tugun uchun buni bajarmaguningizcha takrorlang.
4. Yakuniy yo'lni hisoblang.

**1-qadam**: Eng arzon tugunni toping. Siz boshida turibsiz, A tuguniga yoki B tuguniga o'tish kerakmi, deb o'ylaysiz. Har bir tugunga borish uchun qancha vaqt ketadi?

![a cheap node](/files/5GDCFXdVrmJvCpz8Oxym)

A tuguniga 6 daqiqa, B tuguniga esa 2 daqiqa ketadi. Qolgan tugunlarni siz hali bilmaysiz. Hali marraga yetib borish uchun qancha vaqt ketishini bilmasligingiz sababli, siz cheksizlikni qo'yasiz (nega buni tez orada tushunasiz). B tugun - eng yaqin tugun ... u 2 daqiqa uzoqlikda.

![closest node](/files/s5QyxnxnRKLFWWg2T93C)

**2-qadam**: B tugunining barcha qo'shnilariga qancha vaqt ketishini B tugunining chetiga qarab hisoblang.

![neighbors](/files/73tD3Hs1wPsscQFvzBdk)

Hey, siz A tuguniga qisqaroq yo'lni topdingiz! Ilgari A tuguniga yetib borish uchun 6 daqiqa vaqt ketadi.

![nodes](/files/ps019I75mkv2RcJvWsw3)

Ammo agar siz B tugunidan o'tsangiz, atigi 5 daqiqa davom etadigan yo'l bor!

![nodes](/files/EVe5H9tPZHVmLvOQtjlx)

B ning qo'shnisi uchun qisqaroq yo'lni topsangiz, uning narxini yangilang. Bunday holda siz topdingiz

• A ga qisqaroq yo'l (6 daqiqadan 5 daqiqagacha)

• Marraga qisqaroq yo'l (cheksizlikdan 7 daqiqagacha)

**3-qadam**: takrorlang!

**Yana 1-qadam**: Eng kam vaqt ketadigan tugunni toping. Siz B tugunini bajardingiz, shuning uchun A tugunida keyingi eng kichik vaqt hisobi mavjud.

![node time](/files/pX45hen9wSRAWp49ZgoQ)

**Yana 2-qadam**: A tugunining qo'shnilari uchun xarajatlarni yangilang.

![step 2 again](/files/pr9pHKsv5u5lbS6yhfLC)

Voy, hozir marraga yetib borish uchun 6 daqiqa kerak!

Siz har bir tugun uchun Dijkstra algoritmini ishga tushirdingiz (tugun tugun uchun uni ishga tushirishingiz shart emas). Bu vaqtda, bilasiz

* B tuguniga borish uchun 2 daqiqa vaqt ketadi.
* A tuguniga borish uchun 5 daqiqa vaqt ketadi.
* Marraga yetib borish uchun 6 daqiqa vaqt ketadi.

![node times](/files/KEGbJ9aRGFpB4WSTF0KZ)

Men oxirgi bosqichni, oxirgi yo'lni hisoblab, keyingi bo'lim uchun saqlayman. Hozircha men sizga oxirgi yo'l nima ekanligini ko'rsataman.

![fastest](/files/3De2xJLdjLv1wU5R0dZh)

Kenglikdagi birinchi qidiruv buni eng qisqa yo'l deb topa olmasdi, chunki u uchta segmentga ega. Va ikkita segmentda boshidan oxirigacha borishning bir usuli bor.

![shortest path with bfs](/files/Bbf7BsFGTX9e5H7erwFy)

Oxirgi bobda siz ikkita nuqta orasidagi eng qisqa yo'lni topish uchun kenglik-birinchi qidiruvdan foydalangansiz. O'sha paytda "eng qisqa yo'l" eng kam segmentli yo'lni anglatardi. Ammo Dijkstra algoritmida siz har bir segmentga raqam yoki vazn berasiz. Keyin Dijkstra algoritmi eng kichik umumiy og'irlikdagi yo'lni topadi.

![graphs](/files/GxZUxGMKmZ6D9NlU6cr6)

Xulosa qilib aytganda, Dijkstra algoritmi to'rt bosqichdan iborat:

1. Eng arzon tugunni toping. Bu siz eng kam vaqt ichida kirishingiz mumkin bo'lgan tugun.
2. Ushbu tugunning qo'shnilariga arzonroq yo'l bor-yo'qligini tekshiring. Agar shunday bo'lsa, ularning xarajatlarini yangilang.
3. Grafikdagi har bir tugun uchun buni bajarmaguningizcha takrorlang.
4. Yakuniy yo'lni hisoblang. (Keyingi bo'limda keladi!)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://grokking.realtemirov.uz/7.-dijkstras-algorithm/1.-working-with-dijkstras-algorithm.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.