input license here

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 !
Related Posts
Diệp Quân
Nguyen Manh Cuong is the author and founder of the vmwareplayerfree blog. With over 14 years of experience in Online Marketing, he now runs a number of successful websites, and occasionally shares his experience & knowledge on this blog.
SHARE

Related Posts

Subscribe to get free updates

Post a Comment

Sticky