Ən qısa yol: Dijkstra
BFS weight-siz qrafda ən qısa yolu tapır, çünki orada "ən qısa" = "ən az addım". Weight əlavə olan kimi bu bərabərlik dağılır.
Sadə əks-nümunə: A-dan C-yə iki yol var — birbaşa A → C edge-i (weight 10) və A → B → C yolu (weight 1 + 1 = 2). BFS bir addımlıq birbaşa edge-i seçəcək və 10 qaytaracaq, halbuki əsl ən qısa yol 2-dir. BFS addım sayır, dəyər yox.
Onda niyə "hər edge-i weight qədər hissəyə bölüb yenə BFS işlədək" demirik? Nəzəri olaraq mümkündür, amma weight 1000 olanda bir edge 1000 süni node yaradır — real dataya tətbiq olunmur.
Düzgün cavab Dijkstra alqoritmidir: qonşuları "ən az addım" yox, "indiyə qədər ən ucuz" sırası ilə gəzir. Bunun üçün adi queue əvəzinə priority queue (min-heap) lazımdır — həmişə cari məsafəsi ən kiçik olan node çıxarılır.
Dijkstra-nın işləmə məntiqi üç anlayışdan ibarətdir.
1. `dist` cədvəli — hər node üçün "mənbədən bura indiyə qədər tapılmış ən ucuz məsafə". Başlanğıcda mənbə 0, qalanları sonsuzluqdur.
2. Relaxation — u node-undan v-yə baxıb soruşursan: "dist[u] + weight(u,v) hazırkı dist[v]-dən kiçikdirmi?" Kiçikdirsə, dist[v]-ni yeniləyib v-ni priority queue-ya atırsan. Bütün alqoritm bu bir sətrin təkrarıdır.
3. Greedy invariant — alqoritmin bütün düzgünlüyü buna dayanır: priority queue-dan çıxarılan node-un məsafəsi artıq yekundur, bir daha yaxşılaşmayacaq. Səbəb: qalan bütün yollar ondan da böyük məsafədən başlayır və weight-lər mənfi olmadığına görə yol yalnız uzana bilər.
İki praktik detal, hansı ki, kodda mütləq görünməlidir:
- Stale (köhnəlmiş) girişlər: eyni node queue-ya bir neçə dəfə düşə bilər, çünki adi heap-də "decrease-key" yoxdur. Ona görə çıxarılan girişin məsafəsi
dist-dəkindən böyükdürsə, onu sadəcə atırsan (if (d > dist[u]) continue). Buna lazy deletion deyilir və interview-da bu bir sətrin olması diqqətlə baxılan detaldır - Yolun özünü qaytarmaq: yalnız məsafə deyil, marşrut da lazımdırsa,
prev[v] = ucədvəli saxla və sonda hədəfdən geri gedərək yolu bərpa et
Mürəkkəblik: binary heap ilə O((V + E) log V), adətən O(E log V) kimi yazılır. Yaddaş O(V).
Mənfi weight-lər Dijkstra-nı sındırır və bu, ən çox verilən əlavə sualdır.
Səbəbi greedy invariant-dədir: Dijkstra node-u queue-dan çıxaran kimi onun məsafəsini "yekun" elan edir. Mənfi edge varsa, sonradan tapılan uzun bir yol həmin məsafəni azalda bilər — amma alqoritm o node-a artıq bir daha qayıtmır. Nəticə səssizcə səhv olur; heç bir xəta atılmır və bu, onu təhlükəli edir.
Əks-nümunə: A → B weight 5, A → C weight 2, C → B weight −4. Dijkstra əvvəlcə C-ni (2), sonra B-ni 5 ilə yekunlaşdıra bilər, halbuki əsl cavab 2 + (−4) = −2-dir.
Bu halda Bellman-Ford işlədilir: bütün edge-ləri V − 1 dəfə relax edir, mürəkkəbliyi O(V × E) — Dijkstra-dan xeyli yavaş, amma mənfi weight-lərlə düz işləyir. Üstəlik V-ci iterasiyada hələ də yaxşılaşma varsa, qrafda mənfi cycle olduğunu aşkar edir (belə halda "ən qısa yol" anlayışının özü mənasını itirir, çünki dövrə vurduqca məsafə azalır).
Dəqiqləşdirmə: mənfi weight-lər həmişə "qəribə" məsələ demək deyil — valyuta arbitrajı, enerji balansı, mənfəət/xərc modelləri real nümunələrdir.
| Alqoritm | Nə vaxt istifadə olunur | Mürəkkəblik | Məhdudiyyət |
|---|---|---|---|
| BFS | Weight yoxdur (və ya hamısı bərabərdir) | O(V + E) | Weight-lə səhv nəticə verir |
| Dijkstra | Mənfi olmayan weight-lər, bir mənbədən hamıya | O((V + E) log V) — binary heap ilə | Mənfi weight-lərdə səssizcə səhv işləyir |
| Bellman-Ford | Mənfi weight-lər var; mənfi cycle aşkarlamaq lazımdır | O(V × E) | Xeyli yavaşdır |
| Floyd-Warshall | Bütün cütlər arasında məsafə, kiçik qraf | O(V³) | V böyüyəndə tətbiq olunmur |
| A* | Bir konkret hədəf və yaxşı heuristika var (xəritə, oyun) | Praktikada Dijkstra-dan sürətli | Heuristika düzgün olmalıdır, yoxsa nəticə optimal olmur |
Interview məsləhəti: Dijkstra-nın kodunu əzbər bilmək tələb olunmur — niyə işlədiyini izah etmək tələb olunur. Üç cümlə kifayətdir: "Priority queue ən ucuz node-u verir; onu çıxaranda məsafəsi yekundur, çünki qalan yollar daha uzun məsafədən başlayır və weight-lər mənfi deyil; ona görə hər node bir dəfə yekunlaşır." Bunu deyə bilirsənsə, kodun bir-iki detalını unutmağın problem deyil. Bunu deyə bilmirsənsə, ideal kod da səni xilas etmir — sonrakı sual həmişə "mənfi weight olsa nə dəyişər?" olur.