Đồ Án Nghiên cứu các giải thuật tìm kiếm đường đi ngắn nhất + mã nguồn + demo giải thuật Thuật toán Dijkst

Lý thuyết đồ thị là một lĩnh vực nghiên cứu đã có từ lâu đời và có nhiều ứng dụng hiện đại.Những tư tưởng cơ bản

của lý thuyết đồ thị đươc đề xuất từ những năm đầu của thế kỷ 18 bởi nhà toán học lỗi lạc người Thụy Sĩ Leonhard

Euler. Chính ông là người đã sử dụng đồ thị để giải bài toán nổi tiếng về các cái cầu ở thàng phố Konigsberg.

Đồ thị được sử dụng để giải quyết các bài toán trong nhiều lĩnh vực khác nhau. Chẳng hạn, đồ thị có thể sử dụng để

xác định các mạch vòng trong vấn đề giải tích mạch điện. Chúng ta có thể phân biệt các hợp chất hoá học hữu cơ

khác nhau với cùng công thức phân tử nhưng khác nhau về cấu trúc phân tử nhờ đồ thị. Chúng ta có thể xác định

xem hai máy tính trong mạng có thể trao đổi thông tin được với nhau hay không nhờ mô hình đồ thị của mạng máy

tính. Đồ thị có

trọng số trên các cạnh có thể sử dụng để giải các bài toán như : tìm đường đi ngắn nhất giữa hai thành phố trong

cùng một mạng giao thông . Chúng ta còn sử dụng đồ thị để giải các bài toán về lập lịch, thời khoá biểu và phân bố

tần số cho các trạm phát thanh và truyền hình

Mục đích ta tìm hiểu là nhằm giới thiệu các khái niệm cơ bản, các bài toán ứng dụng quan trọng của lý thuyết đồ thị

như bài toán cây khung nhỏ nhất, bài toán tìm đường đi ngắn nhất . và những thuật toán để giải quyết chúng đã

được trình bày chi tiết cùng với việc phân tích và hướng dẫn cài đặt chương trình trên máy tính.

Bài toán đường đi ngắn nhất nguồn đơn là bài toán tìm một đường đi giữa hai đỉnh sao cho tổng các trọng số của các

cạnh tạo nên đường đi đó là nhỏ nhất. Định nghĩa một cách hình thức, cho trước một đồ thị có trọng số (nghĩa là một

tập đỉnh V, một tập cạnh E, và một hàm trong số có giá trị thực f : E → R), cho trước một đỉnh v thuộc V, tìm một

đường đi P từ v tới mỗi đỉnh v' thuộc V sao cho .