Hỏi về thuật toán tìm đường đi ngắn nhất Bellman - Ford

algorithm

(Summoner's Rift) #1

Mình có làm 1 bài như sau :
trong sách nó giải vậy


nhưng mình thì làm nó ra vậy
image
cho hỏi mình có sai ko vậy mọi người vì ở bước 2 mình thấy điểm 5 chưa thể là -1, 3 ngay được vì lúc này nó mới nối với đỉnh 3,4 mà Mai thi rồi huhu


(Hung) #2

Sách lấy giá trị mới nhất của mảng d.
Khi tính d[5] tại k = 1 thì d[3] = 4 và d[4] = 4 sẵn rồi, chứ không lấy giá trị mảng d tại k = 0.

Nếu nghiên về math thì bạn đúng, mỗi lần lặp là có mảng d mới.
Tuy nhiên, code thật thì không cần phải tuân theo, sử dụng chung mảng d cho tất cả lần lặp k, tiết kiệm bộ nhớ nữa.


(Summoner's Rift) #3

ok hiểu rồi , thanks bro


83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?