Bài 12: Thuật toán Dijkstra

Tham khảo Video sau đây :

1.Đường đi có trọng số

Định nghĩa

• Đồ thị G=(V, E) là đồ thị có trọng số và trọng số mỗi cạnh e là w(e)

• Với G' là một đồ thị con của G thì trọng số của G' được định nghĩa là:

TRONG ĐÓ

• Nếu G' là đường đi hay chu trình thì w(G') gọi là độ dài của G'

• Nếu G' là một mạch (chu trình có các đỉnh không lặp lại) và w(G') < 0 thì G' là mạch âm

Nhận xét

2. Thuật toán Dijkstra

Là một nhà toan học người Hà Lan, đưa ra thuật toán vào năm 1959

Xét đồ thị G=(V, E) có trọng số không âm

• Xét dữ liệu nhập cho thuật toán là ma trận trọng lượng D và hai đỉnh u, v cho trước

• Dữ liệu xuất là đường đi ngắn nhất từ u tới v

3.Code thuật toán

Tham khảo Video sau đây :