Cần giúp đỡ gấp về thuật toán dijkstra

Chào các bạn có thể giúp gấp mình tí về thuật toán Dijkstra, mình sắp thi

Mình làm tới bước 3 xét ‘H’ có một đỉnh kề là ‘K’, mà pi['K'] < L[][]+pi['H'] nên ko xét, nhưng mà kề của ‘H’ chỉ có một đỉnh ‘K’. Thế mình tìm kề của ‘K’ hay quay lại tìm kề của ‘A’, vì kề của ‘A’ có 2 đỉnh’ B’ và ‘C’ có pi = nhau, mình xét theo thứ tự ở bước 1 mình đã xét ‘B’ rùi

AB = 1, AC = 1, AK =4 chọn đại AB coi như AB đã tối ưu
=> AB = 1
từ AB = 1 ==>> AH = ABH = 3, AK = ABK = 4, AG = ABG = 10, AC = 1, chọn C => AC tối ưu
=> AC = 1
từ AB = 1, AC = 1 ==>> AH = ABH = 3, AK = ABK = 4, AG = ABG = 10, AK = ACK = 3, ACD = 8 chọn ACK
=> AK = 3 (ACK)
dựa vào danh sách đã được tối ưu suy ra bước tối ưu kế tiếp
còn cách bạn mô tả thì đúng là đọc không hiểu gì cả

2 Likes

Bonus cho bạn thêm 1 step nữa
từ AB = 1, AC = 1, AK = 3 ==>> danh sách này gồm các đoạn mở rộng của 3 đoạn kia: ABX, ACY, AKZ, X - Y - Z là các đỉnh còn lại
=> AH = ABH = 3
từ AB = 1, AC = 1, AK = 3, AH = 3 ==>>

cho đến khi nào đủ cạnh thì thôi

1 Like

thanks bạn nhé , mình sử dụng code để thử và biết cách nó hoạt đông

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