Edisi pembelajaran bahasa Indonesia. Kode dan keluarannya tetap seperti aslinya.

Algoritma Dijkstra dalam C

Hitung jarak terpendek dari satu simpul pada graf dengan bobot nonnegatif.

Jarak simpul awal adalah nol, sedangkan yang lain belum diketahui atau tak hingga. Pilih simpul belum dikunjungi dengan jarak terkecil, lalu relaksasi sisinya: jika jalur melalui simpul itu lebih pendek, perbarui jaraknya.

Algoritma ini mensyaratkan bobot nonnegatif. Bedakan sisi yang tidak ada dari sisi berbobot nol sesuai representasinya. Jangan menambahkan bobot ke nilai penanda tak hingga dan periksa overflow saat memperluas rentang.

Versi dengan matriks dan pemilihan simpul secara linear biasanya bekerja dalam O(V²). Uji simpul yang tidak terhubung dan jalur alternatif. Bobot negatif memerlukan algoritma lain.

Kode C

#include <stdio.h>
#include <stdbool.h>
#include <limits.h>

#define V 5

int minDistance(int dist[], bool sptSet[]) {
    int min = INT_MAX, min_index = -1;
    for (int v = 0; v < V; v++) {
        if (!sptSet[v] && dist[v] <= min) {
            min = dist[v];
            min_index = v;
        }
    }
    return min_index;
}

void dijkstra(int graph[V][V], int src) {
    int dist[V];
    bool sptSet[V];

    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        sptSet[i] = false;
    }

    dist[src] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;

        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
                && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    printf("Vertex 	 Distance from Source (%d)\n", src);
    for (int i = 0; i < V; i++) printf("%d 		 %d\n", i, dist[i]);
}

int main() {
    int graph[V][V] = {
        {0, 4, 0, 8, 0},
        {4, 0, 8, 11, 0},
        {0, 8, 0, 7, 2},
        {8, 11, 7, 0, 9},
        {0, 0, 2, 9, 0}
    };
    dijkstra(graph, 0);
    return 0;
}

Buka di kompiler

Keluaran yang diharapkan

Vertex 	 Distance from Source (0)
0 		 0
1 		 4
2 		 12
3 		 8
4 		 14

Pertanyaan umum

Mengapa kode dan keluarannya tetap dalam bahasa Inggris?

Kata kunci, pengenal, dan teks yang diperiksa tes dipertahankan agar program tidak berubah. Penjelasan dan kontrol telah diterjemahkan.