TAILIEUCHUNG - bài giảng các chuyên đề phần 9

Lý thuyết đồ thị for i := 1 to n do begin d[i] := c[S, i]; Trace[i] := S; end; FillChar(Free, SizeOf(Free), True); end; procedure Dijkstra; var i, u, v: Integer; min: Integer; begin repeat {Thuật toán Dijkstra} | Lý thuyết đồ thị 62 for i 1 to n do begin d i c S i Trace i S end FillChar Free SizeOf Free True end procedure Dijkstra Thuật toán Dijkstra var i u v Integer min Integer begin repeat Tìm trong các đỉnh có nhãn tự do ra đỉnh u có d u nhỏ nhất u 0 min maxC for i 1 to n do if Free i and d i min then begin min d i u i end Thuật toán sẽ kết thúc khi các đỉnh tự do đều có nhãn x hoặc đã chọn đến đỉnh F if u 0 or u F then Break Cố định nhãn đỉnh u Free u False Dùng đỉnh u tối ưu nhãn những đỉnh tự do kề với u for v 1 to n do if Free v and d v d u c u v then begin d v d u c u v Trace v u end until False end procedure PrintResult In đường đi từ S tới F begin if d F maxC then WriteLn Path from S to F not found else begin WriteLn Distance from S to F d F while F S do begin Write F - F Trace F end WriteLn S end end begin Assign Input Reset Input Assign Output Rewrite Output LoadGraph Init Dijkstra PrintResult Close Input Close Output end. Lê Minh Hoàng Lý thuyết đồ thị 63 V. THUẬT TOÁN DIJKSTRA VÀ CẤU TRÚC HEAP Nếu đồ thị có nhiều đỉnh ít cạnh ta có thể sử dụng danh sách kề kèm trọng số để biểu diễn đồ thị tuy nhiên tốc độ của thuật toán DIJKSTRA vẫn khá chậm vì trong trường hợp xấu nhất nó cần n lần cố định nhãn và mỗi lần tìm đỉnh để cố định nhãn sẽ mất một đoạn chương trình với độ phức tạp O n . Để tăng tốc độ người ta thường sử dụng cấu trúc dữ liệu Heap để lưu các đỉnh chưa cố định nhãn. Heap ở đây là một cây nhị phân hoàn chỉnh thoả mãn Nếu u là đỉnh lưu ở nút cha và v là đỉnh lưu ở nút con thì d u d v . Đỉnh r lưu ở gốc Heap là đỉnh có d r nhỏ nhất . Tại mỗi bước lặp của thuật toán Dijkstra có hai thao tác Tìm đỉnh cố định nhãn và Sửa nhãn. Thao tác tìm đỉnh cố định nhãn sẽ lấy đỉnh lưu ở gốc Heap cố định nhãn đưa phần tử cuối Heap vào thế chỗ và thực hiện việc vun đống Adjust Thao tác sửa nhãn sẽ duyệt danh sách kề của đỉnh vừa cố định nhãn và sửa nhãn những đỉnh tự do kề với đỉnh này mỗi lần sửa nhãn một đỉnh nào đó ta xác định đỉnh này nằm ở .

• Cơ sở dữ liệu
• thuật toán tìm kiếm
• các chuyên đề thuật toán
• lập trình pascal
• lập trình các giải thuật
• Các thuật toán tìm kiếm
• Tìm kiếm trên đồ thị
• Bài toán tìm kiếm trên đồ thị
• Thuật toán tìm kiếm theo chiều rộng
• Thuật toán tìm kiếm theo chiều sâu
• Tìm kiếm tuần tự
• Tìm kiếm nhị phân
• Tìm kiếm dựa trên quy hoạch động
• Tìm kiếm dựa trên đệ quy
• Tìm kiếm dựa trên phân vùng
• Khái niệm tìm kiếm
• Bài toán tìm kiếm
• Tìm kiếm trên dãy chưa sắp
• Cấu trúc dữ liệu
• Kỹ thuật tìm kiếm
• Tìm kiếm trên mảng
• Giải thuật tìm kiếm
• Tìm kiếm trên tập tin
• Tìm kiến tuyến tính
• Thuật toán tìm kiếm tối ưu
• Tìm kiếm cứu nạn
• Thuật toán vi khuẩn
• Tính toán phương án tìm kiếm tối ưu
• Tàu tìm kiếm cứu nạn
• Lý thuyết đồ thị
• Bài giảng Lý thuyết đồ thị
• Thuật toán tìm kiếm trên đồ thị
• Ứng dụng thuật toán tìm kiếm đồ thị
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu và giải thuật
• Khái niệm về tìm kiếm
• Phương pháp tìm kiếm tuần tự
• Phương pháp tìm kiếm nhị phân
• Thuật toán tìm kiếm nhị phân
• Thuật toán tìm kiếm nhị phân cơ bản
• Thuật toán Quicksort
• Cách tìm kiếm nhị phân
• chiến lược tìm kiếm mù
• Tìm kiếm beam
• Tìm kiếm leo đồi
• tìm kiếm tối ưu
• Tìm kiếm có đối thủ
• Tìm kiếm mô phỏng sự tiến hóa
• Thuật toán di truyền
• Bài toán giải thuật
• Chiến lược tìm kiếm
• Tìm kiếm trình tự
• Lập trình C
• Bài giảng Lập trình căn bản
• Bài toán sắp xếp
• Thuật toán tìm kiếm tuần tự
• Thuật toán sắp xếp nổi bọt
• khoa học
• tự nhiên
• toán học
• Các thuật toán tìm kiếm trên đồ thị
• Các giải thuật tìm kiếm
• Giải thuật tìm kiếm tuyến tính
• Giải thuật Tìm kiếm nhị phân
• Các giải thuật sắp xếp
• Tóm tắt Luận án Thạc sĩ
• Hệ thống thông tin
• Tìm kiếm chuỗi DNA
• Tìm kiếm tương tự nhanh
• Bài giảng Toán rời rạc 2
• Toán rời rạc 2
• Toán rời rạc
• Ứng dụng của thuật toán tìm kiếm
• Bài giảng Tìm kiếm heuristic leo đồi
• Thuật giải di truyền
• Thuật giải leo đồi
• Các thuật toán tìm kiếm cục bộ
• Lựa chọn của thuật giải di truyền
• Nội dung về thuật giải leo đồi
• Bài giảng Cấu trúc dữ liệu
• Tìm kiếm trên danh sách
• Tìm kiếm trên văn bản
• Bài giảng Tìm kiếm
• Kỹ thuật lập trình
• Bài giảng Các hệ thống thông minh nhân tạo
• Hệ thống thông minh nhân tạo
• Bài toán tìm kiếm 1
• Cây tìm kiếm
• Thuật toán tìm kiếm mù
• Bài toán tìm đường đi
• Thuật giải HEURISTIC
• phương pháp tìm kiếm HEURISTIC
• thuật toán tìm kiếm leo đồi
• tìm kiếm ưu tiên tối ưu
• ứng dụng giải bài toán ta canh
• chiến lược tìm kiếm lai
• Bài giảng Thuật toán Ứng dụng
• Thuật toán Ứng dụng
• Cấu trúc dữ liệu trừu tượng
• Cài đặt tìm kiếm ở thư viện
• tài liệu học đại học
• bài giảng quy hoạch tuyến tính
• Khoa học máy tính
• tìm kiếm tuyến tính
• Tìm kiếm theo chiều sâu
• Tìm kiếm theo chiều rộng
• Ứng dụng các thuật toán
• Bài giảng Tìm kiếm đối kháng
• Tìm kiếm đối kháng
• Tìm kiếm đối kháng trò chơi
• Thuật toán MINIMAX
• Hàm lượng giá
• Tìm kiếm cắt nhánh