Implementation (Part 1)
Coddy'nin Bellman-Ford Algoritması - Graf Algoritmaları kursunda ders 5 / 9.
İlk olarak, tüm kenarlar üzerinden tek bir gevşetme geçişi.
Görev
OrtaBellman-Ford sadece tekrarlanan bir işlemdir: tüm kenarlar üzerinde bir gevşetme geçişi. Hadi tek bir geçiş oluşturalım.
n, düz edges dizisini (üçlüler, yönlendirilmiş, muhtemelen negatif) ve bir source parametrelerini alan relaxAll adında bir fonksiyon yazın. dist[source] = 0 ve diğer tüm değerler sonsuz olacak şekilde başlayın, ardından her kenarı bir kez (verilen sırayla) gevşetin ve hala ulaşılamayan köşeler için -1 kullanarak sonuç mesafelerini döndürün.
Sadece tek bir geçiş olduğu için, yalnızca birkaç kenar üzerinden ulaşılabilen köşeler hala -1 olabilir. Bu beklenen bir durumdur.
Kendin dene
#include <stdlib.h>
int* relaxAll(int n, int* edges, int edges_size, int source, int* returnSize) {
// Kodu buraya yazın
*returnSize = 0;
return edges;
}
Kendini test etBu ders kısa bir quiz içerir. Soruları yanıtlamak ve ilerlemeni kaydetmek için derse başla.
Bellman-Ford Algoritması - Graf Algoritmaları bölümündeki tüm dersler
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity