Giới thiệu tài liệu
Bài giảng Lý thuyết đồ thị - Chương 5: Bài toán đường đi ngắn nhất là một phần của tài liệu lý thuyết đồ thị, cung cấp cho người đọc những kiến thức về bài toán đường đi ngắn nhất (ĐĐNN), tính chất của ĐĐNN, giảm cận trên và các thuật toán tìm ĐĐNN như Bellman-Ford, Dijkstra, Floyd-Warshal. Bài giảng này được chia thành 6 chương: Bài toán đường đi ngắn nhất, Tính chất của ĐĐNN, Giảm cận trên, Thuật toán Bellman-Ford, Thuật toán Dijkstra, Đường đi ngắn nhất trong đồ thị không có chu trình.
Đối tượng sử dụng
Nhà nghiên cứu, sinh viên lý thuyết đồ thị và những ai có quan tâm đến khoa học về đồ thị
Nội dung tóm tắt
Bài giảng Lý thuyết đồ thị - Chương 5: Bài toán đường đi ngắn nhất cung cấp cho người đọc chi tiết về quy hoạch động, tính chất của bài toán đường đi ngắn nhất (ĐĐNN), giảm cận trên và các thuật toán để tìm đường đi ngắn nhất trong đồ thị. Nội dung bài giảng tập trung vào việc tìm ĐĐNN từ một đỉnh đến tất cả các đỉnh còn lại của đồ thị. Mỗi chương chứa những bài học về ĐĐNN, mô tả chi tiết cách hoạt động của thuật toán Bellman-Ford, Dijkstra, Floyd-Warshal trong quá trình tìm kiếm ĐĐNN. Thuật toán Ford-Bellman được sử dụng khi trọng số của các cung là tuỳ ý và chỉ áp dụng khi đồ thị không có chu trình âm.