Thử thách cuối #1
Bài học 8 trên 9 trong khóa học Thuật toán Bellman-Ford cho đồ thị của Coddy.
Thử thách
Trung bìnhĐiểm mạnh đặc biệt của Bellman-Ford là phát hiện chu trình âm.
Viết một hàm (function) tên là hasNegativeCycle nhận n và mảng edges dạng phẳng (các bộ ba, có hướng), rồi trả về 1 nếu đồ thị có chu trình trọng số âm, hoặc 0 nếu không.
Gợi ý: đặt mọi khoảng cách ban đầu bằng 0, nới lỏng tất cả các cạnh n - 1 lần lặp, rồi thực hiện thêm một lượt nữa. Nếu vẫn có cạnh nào có thể được nới lỏng, thì đồ thị có chu trình âm.
Tự làm thử
#include <stdlib.h>
int hasNegativeCycle(int n, int* edges, int edges_size) {
// Viết code ở đây
return -1;
}
Tất cả bài học trong Thuật toán Bellman-Ford cho đồ thị
Tự luyện tập: Trình biên dịch C online