BÀI TOÁN ÐƯỜNG ÐI NGẮN NHẤT VÀ CHU TRÌNH

 

Lê Thị Thanh Châu^*, Trần Huệ Nương

* Trường Trung học Phổ Thông Lưu Hữu Phước

Trường Ðại học Khoa học Tự Nhiên - ÐHQG tp.HCM

Tóm tắt:

Việc phát hiện ra các chu trình trong một đồ thị có hướng đóng một vai trò quan trọng để lựa chọn một thuật toán thích hợp tìm đường đi ngắn nhất từ một đỉnh đến một đỉnh bất kỳ hay giữa các tập đỉnh của đồ thị có hướng.Bài báo đã nghiên cứu vấn đề này và cho ví dụ để minh họa

CYCLES AND THE SHORTEST PATH PROBLEM

 

Le Thi Thanh Chau^*, Tran Thi Hue Nuong

* Luu Huu Phuoc High School, Cantho

University of Natural Sciences - VNU.HCM

 

Abstract:

 

The shortest path problem is one of the basic and most important problems for graph theory in particular and for operations research in general. Cycles play a crucial role in many algorithms to solve the shortest path problem. This note considers methods for finding cycles in a such graph. Examples are given to illustrate the methods.