Lý thuyết đồ thị – Thuật toán Dijsktra

Cho một đồ thị G = (V, E) với:
– V là tập các đỉnh của đồ thị
– E là tập các cạnh của đồ thị sao cho trọng số các cung d(E) đều > 0.
– và một đỉnh cố định s nằm trong V.
Tìm đường ngắn nhất từ đỉnh s đến mỗi đỉnh v trong V.
Đồ thị trên có thể được biểu diễn bằng một ma trận 2 chiều m[r,c] sao cho mỗi giá trị m[r,c] là trọng số của cung nối đỉnh r và đỉnh c. Nếu không tồn tại cung nối giữa 2 đỉnh, giá trị này bằng 0. Bạn sẽ hiểu rõ hơn trong phần định nghĩa map của mã nguồn.
Thuật toán Dijkstra’s

Mã nguồn thuật toán:


 

No Comments

Post A Comment