Bài toán tìm đường đi ngắn nhất và ứng dụng

ĐẠI HỌC ĐÀ NẴNG

TRƯỜNG ĐẠI HỌC SƯ PHẠM

KHOA TIN

----------

NGUYỄN TIẾN DUY

BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT VÀ

ỨNG DỤNG

KHÓA LUẬN TỐT NGHIỆP

LỜI CẢM ƠN

Trước tiên em xin chân thành cảm ơn toàn bộ giảng viên khoa Tin đã

nhiệt tình dạy bảo và truyền đạt những kiến thức, kinh nghiệm cho em trong bốn

năm học tại trường.

Để có được thành quả ngày hôm nay em xin chân thành cảm ơn sâu sắc

nhất đến thầy Trần Quốc Chiến đã luôn tận tình hướng dẫn, giúp đỡ và động

viên em trong suốt quá trình thực hiện đề tài.

Em cũng xin cảm ơn gia đình, bạn bè đã luôn quan tâm, giúp đỡ về tinh

thần cũng như các phương tiện vật chất góp phần quý báu để hoàn thành đề tài

này.

Một lần nữa em xin gửi đến các Thầy Cô, Gia Đình và Bạn bè lòng biết

ơn chân thành và sâu săc.

Trong quá trình nghiên cứu đề tài dù đã có nhiều cố gắng nhưng không

tránh khỏi những thiếu sót, em rất mong nhận được sự thông cảm và chỉ dẫn

thêm của thầy cô, cùng các bạn.

Em xin chân thành cảm ơn!

Đà Nẵng, tháng 05 năm 2012

Sinh viên

Nguyễn Tiến Duy

ĐẶT VẤN ĐỀ

Ngày nay, sự phát triển của ngành công nghệ thông tin đã góp phần quan trọng

trong sự phát triển của xã hội, nó đã thâm nhập vào mọi đời sống xã hội và có nhiều

ứng dụng rộng rãi trong nhiều lĩnh vực khác nhau như: kĩ thuật, kinh tế, giáo dục, du

lịch .v.v

Lý thuyết đồ thị là một ngành khoa học đã có từ lâu nhưng lại có nhiều ứng

dụng hiện đại. Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó,

nó tỏ ra là công cụ hữu hiệu để mô hình hóa và giải quyết các bài toán trong nhiều lĩnh

vực: khoa học, kĩ thuật, kinh tế, xã hội .v.v

Trên cơ sở những kiến thức đã học được trong môn Lý thuyết đồ thị và sự

hướng dẫn nhiệt tình của thầy Trần Quốc Chiến, tôi đã đi sâu tìm hiểu về các thuật

toán tìm đường đi ngắn nhất trong đồ thị và thấy được tính hữu ích của chúng. Do đó,

tôi đã chọn đề tài nghiên cứu “ Bài toán tìm đường đi ngắn nhất và ứng dụng”.

Tuy nhiên, vì thời gian không cho phép và trình độ có hạn nên tôi chỉ đi vào

nghiên cứu tìm hiểu thuật toán và minh họa cơ bản trên nền web.