Implementasi (Bagian 1)
Pelajaran 5 dari 9 dalam kursus Algoritma Bellman-Ford: Algoritma Graf di Coddy.
Pertama, lakukan satu tahap relaksasi pada semua sisi.
Tantangan
SedangBellman-Ford hanya terdiri dari satu operasi yang diulang: proses relaksasi pada semua edge. Mari buat satu proses.
Tulis fungsi bernama relaxAll yang menerima n, array edges datar (berisi tripel, berarah, mungkin bernilai negatif), dan source. Mulai dengan dist[source] = 0 dan nilai tak hingga untuk semua yang lain, lalu relaksasikan setiap edge satu kali (sesuai urutan yang diberikan) dan kembalikan jarak hasilnya, dengan menggunakan -1 untuk simpul yang masih belum tercapai.
Karena hanya ada satu proses, simpul yang hanya dapat dicapai melalui beberapa edge mungkin masih bernilai -1. Itu memang diharapkan.
Coba sendiri
#include <stdlib.h>
int* relaxAll(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 Bellman-Ford: Algoritma Graf
2Algoritma
Bagaimana cara kerjanya?PseudocodeImplementasi (Bagian 1)Implementasi (Bagian 2)
Kompleksitas Waktu dan RuangLatihan sendiri: Compiler C online