Dijkstra Algoritması
Son güncelleme
Dijkstra algoritması, negatif olmayan kenar ağırlıklarına sahip bir grafta bir kaynak düğümden diğer tüm düğümlere en kısa yolu bulur. Her düğüm için geçici bir mesafe tutar, en küçük geçici mesafeye sahip yerleşmemiş düğümü tekrar tekrar yerleştirir ve kenarlarını gevşetir; mevcut düğüm üzerinden daha kısa bir rota bulunduğunda bir komşunun mesafesini günceller. Her düğüm yerleştikçe mesafelerin düşüşünü izlemek için yukarıdan oynat düğmesine basın.
Temel fikir açgözlüdür: en yakın yerleşmemiş düğüm seçildiğinde mesafesi kesinleşir, çünkü ona giden diğer tüm rotalar zaten daha uzakta olan bir düğümden geçmek zorunda kalır. İkili yığın öncelik kuyruğuyla Dijkstra O((V + E) log V) sürede çalışır. Negatif olmayan ağırlıklar gerektirir; kenarlar negatif olabiliyorsa Bellman-Ford kullanın.
Zaman ve alan karmaşıklığı
| Uygulama | Karmaşıklık | Notlar |
|---|---|---|
| İkili yığın | O((V + E) log V) | Yaygın ve pratik seçim |
| Dizi taraması | O(V²) | Daha basit; yoğun graflar için uygun |
| Alan | O(V) | Mesafeler + öncelik kuyruğu |
| Gerektirir | Negatif olmayan ağırlıklar | Negatif kenarlar açgözlü seçimi bozar |
Adım adım
| Adım | Ne olur |
|---|---|
| 1 | Kaynak mesafesini 0, diğerlerinin hepsini sonsuz olarak ayarlayın. |
| 2 | En küçük geçici mesafeye sahip yerleşmemiş düğümü seçin. |
| 3 | Onu yerleşmiş olarak işaretleyin: en kısa mesafesi artık kesindir. |
| 4 | Her komşu için mevcut-üzerinden-mesafe + kenar ağırlığını hesaplayın. |
| 5 | Bu, komşunun mevcut mesafesinden küçükse onu gevşetin. |
| 6 | Ulaşılabilir tüm düğümler yerleşene kadar tekrarlayın. |
Çözümlü örnek
A-B=4, A-C=1, C-B=2, C-D=5, B-D=1 kenarlarına sahip grafta kaynak A'dan en kısa yollar:
| Adım | Yerleştir | Mesafeler | Eylem |
|---|---|---|---|
| 0 | - | A=0, B=∞, C=∞, D=∞ | Başlat: kaynak A=0, diğerlerinin hepsi sonsuz. |
| 1 | A (0) | B=4, C=1, D=∞ | A'dan kenarları gevşet: B=4, C=1 ayarla. |
| 2 | C (1) | B=3, D=6 | C üzerinden: B=1+2=3, 4'ü geçer; D=1+5=6. |
| 3 | B (3) | D=4 | B üzerinden: D=3+1=4, 6'yı geçer. |
| 4 | D (4) | A=0, C=1, B=3, D=4 | D'yi yerleştir; gevşetilecek bir şey kalmadı. Bitti. |
Dijkstra algoritması ne zaman kullanılır
| Şu durumda kullanın | Şu durumda kaçının |
|---|---|
| Tüm kenar ağırlıkları negatif değilse | Herhangi bir kenar negatif olabiliyorsa: Bellman-Ford kullanın |
| Bir kaynaktan tüm düğümlere en kısa yollara ihtiyacınız varsa | Tüm çiftler arası en kısa yollara ihtiyacınız varsa: Floyd-Warshall daha basittir |
| Graf ağırlıklıysa ve kesin mesafeler istiyorsanız | Graf ağırlıksızsa: düz BFS daha hızlı ve basittir |
| İyi bir yığın veya öncelik kuyruğunuz varsa | Bir sezgiselle tek bir hedefe hızlıca ulaşmak istiyorsanız: A* kullanın |
Dijkstra's Algorithm kodu
Python, JavaScript, Java, C++, C dillerinde temiz ve çalıştırılabilir bir Dijkstra's Algorithm uygulaması. Bir dil seçin, kodu kopyalayın veya Coddy Playground'da hazır yüklenmiş olarak açın.
Python ile Dijkstra's Algorithm kodu
Python
1import heapq2
3
4def dijkstra(graph, start):5 dist = {node: float("inf") for node in graph}6 dist[start] = 07 pq = [(0, start)]8 while pq:9 d, node = heapq.heappop(pq)10 if d > dist[node]:11 continue # stale entry, a shorter path was already found12 for neighbor, weight in graph[node]:13 new_dist = d + weight14 if new_dist < dist[neighbor]:15 dist[neighbor] = new_dist16 heapq.heappush(pq, (new_dist, neighbor))17 return dist18
19
20graph = {21 "A": [("B", 4), ("C", 1)],22 "B": [("D", 1)],23 "C": [("B", 2), ("D", 5)],24 "D": [("E", 3)],25 "E": [],26}27
28for node, d in dijkstra(graph, "A").items():29 print(f"A -> {node}: {d}")JavaScript ile Dijkstra's Algorithm kodu
JavaScript
1const graph = {2 A: { B: 4, C: 2 },3 B: { C: 5, D: 10 },4 C: { E: 3 },5 D: { F: 11 },6 E: { D: 4 },7 F: {},8};9
10function dijkstra(source) {11 const dist = {};12 const visited = new Set();13 for (const node in graph) dist[node] = Infinity;14 dist[source] = 0;15 while (visited.size < Object.keys(graph).length) {16 // JS has no built-in heap: linear scan for the closest node (O(V^2))17 let u = null;18 for (const node in dist) {19 if (!visited.has(node) && (u === null || dist[node] < dist[u])) {20 u = node;21 }22 }23 if (dist[u] === Infinity) break;24 visited.add(u);25 for (const [v, w] of Object.entries(graph[u])) {26 if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;27 }28 }29 return dist;30}31
32console.log("Shortest distances from A:", dijkstra("A"));Java ile Dijkstra's Algorithm kodu
Java
1import java.util.ArrayList;2import java.util.Arrays;3import java.util.List;4import java.util.PriorityQueue;5
6public class Main {7 public static void main(String[] args) {8 int n = 6;9 List<List<int[]>> adj = new ArrayList<>();10 for (int i = 0; i < n; i++) adj.add(new ArrayList<>());11 int[][] edges = {12 {0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 5},13 {2, 3, 8}, {3, 4, 3}, {2, 5, 10}, {4, 5, 2}14 };15 for (int[] e : edges) {16 adj.get(e[0]).add(new int[]{e[1], e[2]});17 adj.get(e[1]).add(new int[]{e[0], e[2]});18 }19
20 int[] dist = new int[n];21 Arrays.fill(dist, Integer.MAX_VALUE);22 dist[0] = 0;23 PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);24 pq.add(new int[]{0, 0}); // {node, distance}25 while (!pq.isEmpty()) {26 int[] cur = pq.poll();27 int node = cur[0], d = cur[1];28 if (d > dist[node]) continue; // stale queue entry29 for (int[] edge : adj.get(node)) {30 int next = edge[0], nd = d + edge[1];31 if (nd < dist[next]) {32 dist[next] = nd;33 pq.add(new int[]{next, nd});34 }35 }36 }37 System.out.println("Shortest distances from 0: " + Arrays.toString(dist));38 }39}C++ ile Dijkstra's Algorithm kodu
C++
1#include <iostream>2#include <queue>3#include <vector>4
5int main() {6 const int INF = 1000000000;7 // Weighted directed graph: adj[u] = {(neighbor, weight), ...}8 std::vector<std::vector<std::pair<int, int>>> adj = {9 {{1, 4}, {2, 1}}, // 010 {{3, 1}}, // 111 {{1, 2}, {3, 5}}, // 212 {{4, 3}}, // 313 {}, // 414 };15 int n = static_cast<int>(adj.size());16 std::vector<int> dist(n, INF);17 dist[0] = 0;18 using State = std::pair<int, int>; // (distance, node)19 std::priority_queue<State, std::vector<State>, std::greater<State>> pq;20 pq.push({0, 0});21 while (!pq.empty()) {22 auto [d, u] = pq.top();23 pq.pop();24 if (d > dist[u]) continue; // stale queue entry25 for (auto [v, w] : adj[u]) {26 if (d + w < dist[v]) {27 dist[v] = d + w;28 pq.push({dist[v], v});29 }30 }31 }32 for (int v = 0; v < n; ++v) {33 std::cout << "Distance 0 -> " << v << ": " << dist[v] << "\n";34 }35 return 0;36}C ile Dijkstra's Algorithm kodu
C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7int main(void) {8 // Weighted directed graph: w[u][v] = 0 means no edge9 int w[N][N] = {10 {0, 4, 1, 0, 0},11 {0, 0, 0, 1, 0},12 {0, 2, 0, 5, 0},13 {0, 0, 0, 0, 3},14 {0, 0, 0, 0, 0},15 };16 int dist[N];17 bool done[N] = {false};18 for (int v = 0; v < N; v++) dist[v] = INF;19 dist[0] = 0;20 // O(V^2) scan for the closest unfinished node (no heap needed here)21 for (int iter = 0; iter < N; iter++) {22 int u = -1;23 for (int v = 0; v < N; v++) {24 if (!done[v] && (u == -1 || dist[v] < dist[u])) u = v;25 }26 if (dist[u] == INF) break; // remaining nodes are unreachable27 done[u] = true;28 for (int v = 0; v < N; v++) {29 if (w[u][v] > 0 && dist[u] + w[u][v] < dist[v]) {30 dist[v] = dist[u] + w[u][v];31 }32 }33 }34 for (int v = 0; v < N; v++) {35 printf("Distance 0 -> %d: %d\n", v, dist[v]);36 }37 return 0;38}Dijkstra Algoritması SSS
Dijkstra algoritmasının zaman karmaşıklığı nedir?
İkili yığın öncelik kuyruğuyla
O((V + E) log V) sürede çalışır. Her adımda minimumu bulmak için bir diziyi tarayan basit sürüm O(V²)'dir ve yoğun graflarda aslında daha hızlı olabilir. İkisi de O(V) alan kullanır.Dijkstra neden negatif kenar ağırlıklarıyla çalışmaz?
Dijkstra, en yakın yerleşmemiş düğümü yerleştirdiğinde o mesafenin kesin olduğunu varsayar. Negatif bir kenar, daha sonra zaten yerleşmiş bir düğüme daha kısa bir yol oluşturarak bu varsayımı bozabilir. Negatif ağırlıklı graflar için Bellman-Ford algoritmasını kullanın.
Dijkstra ile BFS arasındaki fark nedir?
BFS, kenarları sayarak (her kenar ağırlığı etkin olarak 1) düz bir kuyruk kullanarak en kısa yolları bulur. Dijkstra bunu ağırlıklı graflara genelleştirir; her zaman en küçük toplam mesafeye sahip düğümü bir öncelik kuyruğu kullanarak genişletir. Ağırlıksız bir grafta ikisi de aynı yolları üretir.
Dijkstra ile A* araması arasındaki fark nedir?
A*, bir hedefe kalan mesafeyi tahmin eden bir sezgisel eklenmiş Dijkstra'dır; böylece her yöne eşit yayılmak yerine aramayı o hedefe yönlendirir. Sezgisel sıfır olduğunda A*, tam olarak Dijkstra'ya dönüşür. Tek bir hedefiniz ve iyi bir kabul edilebilir sezgiseliniz varsa A* kullanın; tüm düğümlere mesafelere ihtiyacınız varsa Dijkstra kullanın.
Bellman-Ford yerine ne zaman Dijkstra kullanmalıyım?
Tüm kenar ağırlıkları negatif olmadığında her zaman Dijkstra kullanın: Bellman-Ford'un
O(V·E)'sine karşı O((V + E) log V) ile daha hızlıdır. Bellman-Ford'u yalnızca kenarlar negatif olabildiğinde veya negatif döngüleri tespit etmeniz gerektiğinde seçin. Negatif olmayan graflarda Dijkstra neredeyse her zaman daha iyi seçenektir.Dijkstra bir düğümü yerleştirdikten sonra tekrar ziyaret edebilir mi?
Hayır: bir düğüm yerleştirildiğinde mesafesi kesinleşir ve bir daha asla gevşetilmez. Yığın uygulamalarında yaygın bir tuzak, bir düğümün mesafesi iyileştikten sonra öncelik kuyruğunda eski girişler bırakmaktır; çıkarılan bir düğüm zaten yerleşmişse (çıkarılan mesafesi kaydedilen mesafeyi aşarsa) onu atlamalısınız. Bu kontrolü unutmak yine de doğru yanıtlar verir ama boşa iş yaptırır.
İlgili kaynaklar
Daha fazla görselleştirme
