Thuật toán Dijkstra sử dụng heap

[dieucay555]

Có ai đã cài đặt thuật toán dijkstra trên heap chưa,có thể giúp mình được không?

[NgôiSaoMayMắn]

Bạn cài heap tăng. Phần tử của heap là 1 cấu trúc (NodeId, value). Thành phần value dùng để sắp xếp heap.
1. Bỏ nút bắt đầu vô heap
2. Nếu heap chưa rỗng thì V = Heap.Pop() ngược lại bật cờ ko tìm thấy và nhảy đến bước 7.
3. Nếu V.NodeId chưa được duyệt tiếp bước 4. Ngược lại đến bước 2.
4. Đánh dấu node V.NodeId đến bước 5.
5. V.NodeId là nút đích thì bật cờ tìm thấy và nhảy đến bước 7. Ngược lại đến bước 6.
6. Từ nút V tính khoảng cách cho các nút lân cận. Mỗi khí tính xong một nút thì bỏ vô heap. Đến bứoc 2.
7. Dựa vào cờ để kết luận kết quả tìm kiếm.