Dijkstra Algoritması

Graflar O(V²) O(V)

Negatif olmayan kenarlı ağırlıklı bir grafta kaynak düğümden diğer tüm düğümlere en kısa yolu bulur.

Kaynak

1/28

Tüm mesafeler ∞ olarak başlatılıyor.

DeğişmezZiyaret edilen her düğümün en kısa mesafesi nihaidir. Bu ancak hiçbir kenar ağırlığı negatif değilse geçerlidir.

mevcutsınırziyaret edildiağaç kenarı

dijkstra.c

#define V 6
#define INF 1000000
 
void dijkstra(int graph[V][V], int src, int dist[V]) {
    int visited[V] = {0};
    for (int i = 0; i < V; i++) dist[i] = INF;
    dist[src] = 0;
 
    for (int count = 0; count < V - 1; count++) {
        int u = -1;
        for (int v = 0; v < V; v++)
            if (!visited[v] && (u == -1 || dist[v] < dist[u]))
                u = v;
        visited[u] = 1;
 
        for (int v = 0; v < V; v++)
            if (graph[u][v] && !visited[v] &&
                dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }
}

Dijkstra Algoritması nasıl çalışır?

Kesin en kısa mesafesi bilinen düğümler kümesini büyüt. Her adımda geçici mesafesi en küçük ziyaretsiz düğümü kesinleştir ve kenarlarını gevşet — kenarlar negatif olmadığından kesinleşen mesafe bir daha iyileşemez.

En kötü durum

Buradaki dizi taramasıyla O(V²); öncelik kuyruğuyla O(E log V).

Ne zaman kullanılır?

Negatif olmayan ağırlıklarla tek kaynaklı en kısa yol: rotalama, haritalar, ağ maliyetleri.