Triển khai (phần 2)
Bài học 6 trên 9 trong khóa học Thuật toán Bellman-Ford cho đồ thị của Coddy.
Bây giờ, lặp lại lượt này cho đến khi các khoảng cách không còn thay đổi.
Thử thách
Trung bìnhGiờ là toàn bộ thuật toán: lặp lại lượt nới lỏng cho đến khi các khoảng cách ổn định.
Viết một hàm có tên bellmanFord, nhận n, mảng edges phẳng (các bộ ba, có hướng, có thể có trọng số âm) và source, rồi trả về khoảng cách ngắn nhất từ source đến mọi đỉnh. Dùng -1 cho các đỉnh không thể đến được. Giả sử không có chu trình âm.
Nới lỏng tất cả các cạnh n - 1 lần.
Tự làm thử
#include <stdlib.h>
int* bellmanFord(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