Implementasi (Bagian 2)
Pelajaran 6 dari 9 dalam kursus Algoritma Dijkstra: Algoritma Graf di Coddy.
Sekarang, perhitungan jalur terpendek yang rakus.
Tantangan
SedangSekarang susun algoritma lengkapnya.
Tulis fungsi bernama dijkstra yang menerima n, array edges datar (triple, berarah, bobot non-negatif), dan source, lalu mengembalikan array dengan posisi v berisi jarak terpendek dari source ke v. Gunakan -1 untuk simpul yang tidak dapat dijangkau.
Mulai dengan semua jarak bernilai "infinity" yang besar, kecuali jarak sumber yang bernilai 0. Lalu, sebanyak n kali, tetapkan simpul belum dikunjungi yang paling dekat, kemudian relaksasikan sisi-sisi keluarnya.
Coba sendiri
#include <stdlib.h>
int* dijkstra(int n, int* edges, int edges_size, int source, int* returnSize) {
// Tulis kodemu di sini
*returnSize = 0;
return edges;
}
Uji dirimuPelajaran ini berisi kuis singkat. Mulai pelajarannya untuk menjawab kuis dan melacak progresmu.
Semua pelajaran di Algoritma Dijkstra: Algoritma Graf
2Algoritma
Bagaimana cara kerjanya?Kode SemuImplementasi (Bagian 1)Implementasi (Bagian 2)
Kompleksitas Waktu dan RuangLatihan sendiri: Compiler C online