tailieunhanh - Bài giảng Thiết kế và đánh giá thuật toán: Đường đi ngắn nhất - TS. Lê Nguyên Khôi

Bài giảng "Thiết kế và đánh giá thuật toán: Đường đi ngắn nhất" cung cấp cho người học các kiến thức: Đường đi, tính chất đường đi ngắn nhất, đường đi ngắn nhất từ một đỉnh, đường đi ngắn nhất giữa mọi đỉnh. . | Thiết Kế & Đánh Giá Thuật Toán Đường Đi Ngắn Nhất TS. Lê Nguyên Khôi Trường Đại Học Công Nghệ - ĐHQGHN Nội Dung Đường đi Tính chất đường đi ngắn nhất Đường đi ngắn nhất từ một đỉnh Thuật toán Dijkstra Đường đi ngắn nhất giữa mọi đỉnh Thuật toán Floyd–Warshall 1 Đường Đi – Định Nghĩa Trong đồ thị vô hướng = , Đường đi là dãy các đỉnh , , , 2 đỉnh liên tiếp , được nối bởi 1 cạnh trong . được gọi là đường đi từ đến Chu trình là đường đi , , , với > 1 trong đó đỉnh đầu tiên phân biệt và = Với đồ thị có hướng, trong một đường đi hay chu trình, 2 đỉnh liên tiếp ( , ) phải là một cung thuộc 2 Đường Đi – Trọng Số Đồ thị có hướng = , với hàm trọng số cung : → . Trọng số của đường đi → → ⋯ → được định nghĩa: , Ví dụ: 2 3 Đường Đi Ngắn Nhất – Định Nghĩa Đường đi ngắn nhất (ĐĐNN) từ đến là đường đi có trọng số nhỏ nhất từ đến . Trọng số đường đi ngắn nhất từ đến được định nghĩa: , = min : đường đi từ đến Chú ý: , = ∞ không tồn tại đường đi từ đến .