Timtailieu.net 
Phân tích tư tưởng của nhân dân qua đoạn thơ: Những người vợ nhớ chồng… Những cuộc đời đã hóa sông núi ta trong Đất nước của Nguyễn Khoa Điềm
3403
1
0
9 trang
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. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
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ôiThiết Kế & Đánh Giá Thuật ToánĐường Đi Ngắn NhấtTS. Lê Nguyên KhôiTrường Đại Học Công Nghệ - ĐHQGHNNộ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–Warshall1Đường Đi – Định NghĩaTrong đồ 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 haychu trình, 2 đỉnh liên tiếp ( , ) phải là mộtcung 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ụ: 23Đườ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đitừđếnChú ý: , = ∞không tồn tại đường đitừ đến .4
