Weight’ga ega DAGlarda shortest path’ni topish

Graph

Endi biz DAGlar (directed acyclic graph) uchun shortest path‘ni topishni ko’rib chiqamiz. Aslida DAGlar uchun Dijkstra’ning algoritmi ham ishlayveradi, ammo bizdagi graph‘ning acyclic, ya’ni aylanasi yo’q ekanligini bilar ekanmiz, bu bizga shortest path’ni topish ishini yengillashtiradimi?

Qisqa javob – ha, shortest path’ni topish uchun, avval vertex’larni topological sort tartibida olib, ularga navbatma-navbat edge relaxation qo’llab chiqiladi. Graph DAG bo’lgani uchun, bizda aylanalar, ko’rilgan vertex’ga qaytib kelish ehtimoli bo’lmaydi. Topological sort va edge relaxation kombinatsiyasi bo’lgan algoritmning nomini acyclic shortest path deb ham ataladi.

Acyclic shortest path’ning Dijkstra algoritmidan qanday ustunlik taraflari bor?

  • Boshlang’ich vertexdan boshqa vertex’larga qisqa yo’lni linear vaqt ichida topadi.
  • Negativ weight’li edge’lar uchun ham ishlaydi. Dijkstra algoritmi negativ weight’lar uchun ishlamaydi.
  • Longest path’ni topish (shortest path’ning teskarisi) masalalarida ham qo’l keladi.

Shortest path’ni topish uchun Dijkstra algoritmida ko’rib chiqqan graph’imiz DAG bo’lgani uchun bu yerda ham undan misol sifatida foydalanamiz.

Graph uchun vertex’larning topological tartibi (topological sort’ni topish haqida):

[ 0, 1, 4, 7, 5, 2, 3, 6 ]

Biz har bir vertex uchun edge relaxation amalini qo’llab chiqamiz. Masofa va bog’lanishlarni odatdagidek distTo[] hamda edgeTo[] ga yig’ib boramiz.

Topological sort’dagi tartibga ko’ra, tekshirishni 0 vertex’dan boshlaymiz. 0 dan 1, 7 va 4 vertex’larga edge bor. Ular uchun 0 vertex’dan masofani hisoblaymiz.

vdistToedgeTo
00
150
2
3
490
5
6
780

Topological sort’dagi keyingi vertex – 1. 1 vertexdan davom ettiramiz.

1 dan 3, 2, 7 vertex’ga edge bor. Ular uchun boshlang’ich nuqta – 0 vertex’dan masofani hisoblaymiz.

vdistTo[]edgeTo[]
00
150
25 + 12 = 171
35 + 17 = 201
490
5
6
780

0 -> 1 -> 7 masofasi = 9 chiqdi. Bizdagi 0 -> 7 masofa kichikroq – 8 ga teng. Shuning uchun 7 ga masofani yangilamaymiz. Faqat yangi masofa eskisidan kichik bo’lgandagina yangilanadi.

Keyingi vertex – 4. 4 dan 5, 6, 7 ga edge bor. Ular uchun boshlang’ich nuqta – 0 vertex’dan masofani hisoblaymiz.

vdistTo[]edgeTo[]
00
150
2171
3201
490
59 + 4 = 134
69 + 20 = 294
780

Keyingi vertex – 7. 7 dan 2 va 5 vertex’ga edge bor. Ular uchun boshlang’ich nuqta – 0 vertex’dan masofani hisoblaymiz. 2-vertex uchun edge relaxation ishladi.

vdistTo[]edgeTo[]
00
150
217 8 + 7 = 157
3201
490
5134
6294
780

Keyingi vertex – 5. 5 dan 2 va 6 vertex’ga edge bor. Ular uchun boshlang’ich nuqta – 0 vertex’dan masofani hisoblaymiz. 2 va 6 vertex’lar uchun edge relaxation ishladi.

vdistTo[]edgeTo[]
00
150
215 13 + 1 = 145
3201
490
5134
629 13 + 13 = 265
780

Keyingi vertex – 2. 2 dan 3 va 6 vertex’ga edge bor. Ular uchun boshlang’ich nuqta – 0 vertex’dan masofani hisoblaymiz. 3 va 6 vertex’lar uchun edge relaxation ishladi.

vdistTo[]edgeTo[]
00
150
2145
320 14 + 3 = 172
490
5134
626 14 + 11 = 252
780

Keyingi vertex – 3. 3 dan 6 vertex’ga edge bor. 0 dan 3 orqali 6 borish, 2 orqali borishdan kattaroq masofaga ega, shu sababli 6 yangilanmaydi.

Ohirgi vertex – 6 ning edge’lari yo’q, demak hisoblashlar tugadi. Yakuniy jadval quyidagicha bo’ladi.

vdistToedgeTo
00
150
2145
3172
490
5134
6252
780

Biz Dijkstra algoritmida bo’lgani kabi, bir xil natijaga erishdik:

Longest path qanday topiladi?

  • Barcha weight’larni negativ qilib olinadi (weight * -1)
  • Shortest path’lar topiladi
  • Natijadagi weight’larni yana negativ qilib olinadi.

Shunda, minus qiymatdagi shortest path’lar plyusga aylantirilganda longest path’lar paydo bo’ladi.

Kod

Longest path’ni topish uchun graph’ga edge berish vaqtida negativ qiymatga o’zgartirish kifoya:

// Add weight
edge.set('weight', item[1] * -1)

Keyin distTo qiymatlarini agar keyinchalik ishlatilsa, u ham negativ qiymatga o’zgartiriladi. Aniqrog’i distTo dagi minusli weight’lar -1 ga ko’paytirilib, plyus qiymatga aylantiriladi.

Kod Githubda:
DAG shortest path: https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/graphs/shortest-path/dag-shortest-path.js
DAG longest path: https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/graphs/shortest-path/dag-longest-path.js

* * *

Mavzu bo’yicha savollarni Github’dagi Webmaxor / leetcode-solutions repository’da yozishingiz yoki kodda Reference in new issue ni bosib, qoldirishingiz mumkin.