Thuật Toán Dijkstra - Đường Đi Ngắn Nhất Trên Đồ Thị

THUẬT TOÁN DIJKSTRA

Cho một đồ thị vô hướng liên thông, thuật toán Dijkstra sẽ giúp bạn tìm ra đường đi ngắn nhất từ một đỉnh bất kì đến các đỉnh còn lại.

Thuật Toán Dijkstra - Đường Đi Ngắn Nhất Trên Đồ Thị

THUẬT TOÁN

MÔ TẢ THUẬT TOÁN:

• Bước khởi tạo: Chọn một đỉnh làm đỉnh xuất phát sau đó tính khoảng cách từ đỉnh ban đầu đến các đỉnh còn lại. ( Nếu không có cạnh nào nối 2 đỉnh thì cho bằng vô cùng)
• Bước 1: Lấy đỉnh có đường đi ngắn nhất đã tính ở trên rồi đánh dấu đỉnh đó đã tìm được đường đi ngắn nhất.
• Bước 2: Từ đỉnh đó tính đường đi đến các đỉnh còn lại. Nếu tại 1 đỉnh phát hiện đường đi ngắn hơn đường đi tìm được ở bước trên thì cập nhật lại đường đi
• Lặp lại bước 2, 3 đến khi tìm được đường đi ngắn nhất tới tất cả các đỉnh.
• In ra đường  đi ngắn nhất đến tất cả các đỉnh
• Ngôn ngữ: C++

ĐỒ THỊ MẪU:

Đồ Thị Vô Hướng Liên Thông

CODE MẪU:

KẾT QUẢ:

distance 1->1 = 0
distance 1->2 = 7
distance 1->3 = 7
distance 1->4 = 4
distance 1->5 = 6
distance 1->6 = 3

LỜI KẾT

Trên đây mình đã chia sẻ những hiểu biết của mình về thuật toán Dijkstra. Nếu có gì sai sót các bạn có thể để lại comment ở bên dưới để mình chỉnh sửa. Cảm ơn các bạn đã đọc bài viết !

Đánh Giá Bài Viết: