Triển khai (phần 1)
Bài học 5 trên 9 trong khóa học Thuật toán Bellman-Ford cho đồ thị của Coddy.
Đầu tiên, thực hiện một lượt thư giãn duy nhất qua tất cả các cạnh.
Thử thách
Trung bìnhBellman-Ford chỉ gồm một thao tác được lặp lại: một lần duyệt nới lỏng trên tất cả các cạnh. Hãy tạo một lần duyệt.
Viết một hàm (function) tên là relaxAll, nhận n, mảng edges dạng phẳng (các bộ ba, có hướng, có thể có trọng số âm) và source. Bắt đầu với dist[source] = 0 và tất cả các giá trị khác là vô cực, sau đó nới lỏng từng cạnh đúng một lần (theo thứ tự đã cho) rồi trả về các khoảng cách thu được, dùng -1 cho những đỉnh chưa tới được.
Vì chỉ có một lần duyệt, các đỉnh chỉ có thể tới được qua nhiều cạnh vẫn có thể mang giá trị -1. Điều đó là bình thường.
Tự làm thử
#include <stdlib.h>
int* relaxAll(int n, int* edges, int edges_size, int source, int* returnSize) {
// Viết code ở đây
*returnSize = 0;
return edges;
}
Tự kiểm traBài học này có một bài trắc nghiệm ngắn. Bắt đầu bài học để trả lời và theo dõi tiến độ.
Tất cả bài học trong Thuật toán Bellman-Ford cho đồ thị
2Thuật toán
Cách hoạt động?Mã giảTriển khai (phần 1)Triển khai (phần 2)
Độ phức tạp thời gian và không gianTự luyện tập: Trình biên dịch C online