Các Thuật Toán Về Tìm Đường Đi Ngắn Nhất Với Giải Thuật Dijkstra

Thuật toán Dijkstra là một trong những thuật toán cổ xưa để giải quyết và xử lý bài toán tìm lối đi ngắn nhất xuất phát điểm từ 1 điểm mang lại trước tới tất cả các điểm còn sót lại trong đồ gia dụng thị có trọng số. Trong nội dung bài viết này họ cùng khám phá ý tưởng cơ bản của thuật toán Dijkstra.

Bạn đang xem: Tìm đường đi ngắn nhất

Mục lục 2. Lấy một ví dụ 1. Ý tưởng

Thuật toán Dijkstra rất có thể giải quyết vấn đề tìm lối đi ngắn duy nhất trên đồ thị vô phía lẫn được bố trí theo hướng miễn là trọng số không âm.

Ý tưởng cơ bản của thuật toán như sau:

Bước 1: trường đoản cú đỉnh gốc, khởi tạo khoảng cách tới chủ yếu nó là $0$, khởi tạo khoảng chừng cách nhỏ dại nhất ban đầu tới những đỉnh không giống là $+infty$. Ta được list các khoảng cách tới các đỉnh.Bước 2: chọn đỉnh a có khoảng cách bé dại nhất trong list này và ghi nhận. Các lần sau sẽ không còn xét cho tới đỉnh này nữa.

Xem thêm: Hình Xăm 3D Đẹp Cho Nam Nữ ❤️ 1001 Tattoo 3D Mini, Hình Xăm Nhện 3D Giá Bao Nhiêu Tiền

Bước 3: theo lần lượt xét các đỉnh kề b của đỉnh a. Nếu khoảng phương pháp từ đỉnh gốc cho tới đỉnh b nhỏ dại hơn khoảng cách hiện tại đang được ghi nhấn thì update giá trị cùng đỉnh kề a vào khoảng cách hiện trên của b.Bước 4: sau khi xét tất cả đỉnh kề b của đỉnh a. Lúc này ta được danh sách khoảng cách tới các điểm đã làm được cập nhật. Quay lại Bước 2 với list này. Thuật toán kết thúc khi chọn được khoảng cách bé dại nhất từ tất cả các điểm.2. Ví dụ

Để dễ dãi hiểu ý tưởng của thuật toán. Họ cùng xem lấy ví dụ như với đồ dùng thị vô hướng $G$. Thuật toán Dijkstra vẫn tìm khoảng cách từ đỉnh gốc $0$ tới toàn bộ các đỉnh còn lại trong thiết bị thị $G$.

Đồ thị $G$

Đầu tiên, khởi tạo khoảng cách nhỏ dại nhất ban sơ tới những đỉnh không giống là $+infty$ và khoảng cách tới đỉnh gốc là 0. Ta được danh sách các khoảng cách tới các đỉnh.