Algorithm: Floyd–Warshall và bài toán đường đi ngắn nhất giữa mọi cặp đỉnh trên đồ thị

Thuật toán Floyd-Warshall hay còn gọi là Floyd, Roy-Floyd là thuật toán tìm đường đi ngẵn nhất giữa mọi cặp đỉnh trong đồ thị có trọng số được công bố năm 1962 bởi Robert Floyd . Trong bài này tôi sẽ giới thiệu cách cài đặt thuật toán này trong chương trình Y2 Visual Graph đã giới thiệu trước đây.

Tiếp tục đọc

Advertisements

Algorithm – Minh họa tìm đường đi ngắn nhất với Breadth First Search trong C#

Tìm đường đi ngắn nhất là một trong những bài toán được ứng dụng trong nhiều lĩnh vực. Và một thuật toán cơ bản và đơn giản nhất để làm điều này mà bạn có thể đã biết là Breadth First Search (BFS – Tìm kiếm theo chiều rộng). Cơ chế làm việc của thuật toán tương tự như vết dầu loang, tìm kiếm những điểm gần nhất trước. Bạn có thể thấy một vài game sử dụng bản đồ hay liên quan đến AI cũng có thể sử dụng thuật toán này. Một ví dụ bạn có thể áp dụng thuật toán này là n-puzzle mà tôi đã cài đặt bằng thuật toán A* để giải quyết.

Tiếp tục đọc