tailieunhanh - Phần tích thiết kế giải thuật (phần 4)

Trong lập trình từ lâu đã đề cấp đến những giải pháp tìm đường đi ngắn nhất từ một địa điểm này đến một địa điểm kia và đã có rất nhiều thuật toán được đưa ra, và trong tài liệu này các bạn cũng có thể làm quen với một số thuật toán cơ bản về tìm đường đi ngắn nhất rất quan trọng đối với học sinh ngành công nghệ thông tin | Chương 3. Bài toán tìm đường đi ngan nhất. CHƯƠNG 3. BÀI TOÁN TÌM ĐƯỜNG ĐI NGAN NHÁT. Những bài toán tìm đường đi trong các đồ thị đặc biệt là tìm đường đi ngan nhất đữờc kệ lá một trong những bái toán kinh điện cồ trong ly thuyết đồ thị vá cồ nhiệu ững dụng nhát. . ĐỊNH NGHĨA. Cho G X U lá mọt đo thị co định giá tữờng ững vời moi cung u i j co mọt chiếu dái háy trong lữờng l u háy lij . Bái toán tìm đữờng đi ngán nhất giữá i vá j lá tìm mọt đữờng p i j tữ i đến j sáo cho 1 b s 1 u u lá ngán nhát. Diễn giải l p Chi chí ván chuyện Chi phí xáy dững thời gián cán thiết đệ đi khấp . CHU Y. Bái toán tìm đữờng đi ngán nhất tữờng tữ vời bái toán tìm đữờng đi dái nhát. Những thuát toán khác nháu thệo những tính chất sáu đáy 1 u 0 V u e U. l u báng nháu l u 1 V u e U. Bái toán đữờng đi ngán nhát thệo sô cung G không co chu trình. G Trương Mỹ Dung G và 1 u bất kỹ. 33 Chương 3. Bài toán tìm đường đi ngan nhất. Và loại bài toán sau được xét Tìm đưông đi ngàn nhát tư một đỉnh đến các đỉnh con lại Tìm đưông đi ngàn nhát giưa các cạp đỉnh. . NGUYÊN LY TOI ƯU. Nguyén ly toi ưu phát biếu théo sự kiến lá táp đưông đi con cUá táp đưông đi ngán nhất lá nhưng đưông ngán nhát. Bổ ĐÊ. Xét đồ thị G X U và một hàm trong lương l X x X R Cho C X1 X2 . Xk là đường đi ngàn nhất tư X1 đến Xk và với mội i j sàồ cho 1 i j k Cho Cij Xi Xi 1 . Xj là đường con củà C tư Xi đến Xj. Khi ấy Cij là mọt đường ngàn nhất tư Xi đến Xj. Nguyén ly củá nhưng thuật toán tìm đưông đi ngán nhất Mọt khoáng cách d i tượng ưng vôi đỉnh Xj. Ở cuối thuât toán khoáng cách náy biếu dién chiếu dái ngán nhất tư gôc đến đỉnh đáng xét. . CÁC DANG CUA BAI TOAN TỪ MỘT ĐỈNH ĐEN CÁC ĐỈNH CÒN LAI. Bái toán náy con được goi lá bái toán tìm đưông đi ngán nhất tư gôc duy nhất. Nhiếu bái toán khác cung co thế dung thuât toán náy đế giái Đưông đi ngán nhát đến đích duy nhất. Đưông đi ngán nhát tư cặp đỉnh cho trưôc. Đưông đi ngán nhát cho moi cáp đỉnh thuát toán gôc duy nhát tư moi đỉnh . Trương Mỹ Dung 34 Chương 3. Bài toán