MỞ ĐẦU

Trong thực tế ta thường sữ dụng đến mạng lưới điện thoại, giao thông (đặc biệt là đường hàng không), mạng máy tính . Chúng giữ một vị trí rất quan trọng trong cuộc sống. Việc nghiên cứu và phát triễn kỹ thuật luôn được chú trọng, nhằm giải quyết các công việctrong những lĩnh vực này một cách linh hoạt, ví dụ như giãm chi phí it1 tốn kém thời gianvà còn nhiều hiệu quả. Để giải quyết những tổn hao đó, việc nghiên cứu phải dựa trên ngành toán học đó là lý thuyết đồ thị (GRAPH THEORY ) hay nói một cách chung lý thuyết đồ thị là một công cụ toán học xây dựng mô hình cho các vấn đề trên.

Như ta đả biết một mạng điện thoại, mạng máy tính hay một mạng thông tin nói chung thường có một cấu trúc chung đó là các điểm liên hệ với nhau. Để mô hình sự liên hệ này, trong toán học lý thuyết đồ thị sẽ biễu diển bởi một đồ thị, trong đó đỉnh của đồ thị là điểm thông tin, cạnh của đồ thị là sự liên hệ củaác điểm thông tin, số được gán trên cạnh của đồ thị và biễu diễn khoãng cách hay chi phí các nút thông tin.

Để hiểu được các qui tắc giãm được thời gian và chi phí trên các ứng dụng thực tế cũng như lý thuyết thì đề tài này là “tìm hiểu các giải thuật tìm đườngđi ngắn nhất bằng lý thuyết và thực tế, rồi mô phõng trên môi trường đồ họa của windows”.

Nội dung đưa ra những giải thuật tìm đường đi ngắn nhất giữa hai đỉnh nguồn (X) và đỉnh đích (Y) nào đó và dùng các giải thuật đó để mô phõng trên môi trường đồ họa windows.

Bài toán tìm đường đi ngắn nhất là một bài toán lớn và được ứng dụng trong nhiều lĩnh vực, đặc biệt là tìm đường đi trong hệ thống giao thông. Đã có nhiều giải thuật tuần tự cũng như song song được đưa ra để giải quyết vấn đề này. Bên cạnh đó còn có giải thuật tìm đường tĩnh và tìm đường động cũng được đưa ra giải quyết vấn đề này.

Bài toán tìm đường đi có nhiều dạng, chẳng hạn như tìm đường đi của đồ thị có hướng, vô hướng, trọng số của đồ thị có thể là khoảng cách giữa hai node hay chi phí để đi từ node này đến node kia.

Trong đề tài này em sử dụng phần mềm VISUALL C++, để hiện thực các giải thuật: Dijsktra, Bellman Ford, Shorttest Path Routing, Floyd. Để từ đó đánh giá xem việc tìm đường bằng lý thuyết được thực tiển không.

Đề tài này gồm hai phần:

PHẦN I:

Tìm hiểu các giải thuật tìm đường tỉnh .

PHẦN II:

Mô phỏng các giải thuật trên môi trừơng đồ hoạ windows