Đang chuẩn bị liên kết để tải về tài liệu:
Đồ thị và các thuật toán – Chương 3: Các bài toán về đường đi

Đồ thị và các thuật toán – Chương 3: Các bài toán về đường đi. Nội dung chính trong chương này gồm có: Đường đi giữa hai đỉnh, đường đi ngắn nhất giữa hai đỉnh, đường đi ngắn nhất giữa tất cả các cặp đỉnh, phát hiện mạch có độ dài âm. để biết thêm nội dung chi tiết. | Đồ thị và các thuật toán – Chương 3: Các bài toán về đường đi Chu.o.ng 3 C´ ac b` ai to´ an vˆ ¯u.` `e d o.ng d ¯i Trong c´ac u ´.ng du.ng thuc tˆe´, ta cˆ`an t`ım d¯u.`o.ng d¯i (nˆe´u c´o) gi˜ u.a hai d¯ı˙’nh cu˙’a d¯`oˆ thi D - ˇa.c . . biˆe.t, b`ai to´an t`ım d¯u `o ng d¯i ngˇa´n nhˆa´t gi˜ . u a hai d¯ı˙’nh cu˙’a mˆo.t d¯`oˆ thi. c´o y . ´ ngh˜ıa to l´o n. C´o ˙ ’ ˜ thˆe dˆan vˆ . `e b`ai to´an nhu vˆa.y t` . u nhiˆ . `eu b`ai to´an thu. c tˆe´. V´ı du., b`ai to´an t`ım h`anh tr`ınh tiˆe´t kiˆe.m nhˆa´t (theo tiˆeu chuˆa˙’n khoa˙’ng c´ach, th`o.i gian hoˇa.c chi ph´ı) trˆen mˆo.t ba˙’n d¯`oˆ giao thˆong; b`ai to´an cho.n phu.o.ng ph´ap tiˆe´t kiˆe.m nhˆa´t d¯ˆe˙’ d¯u.a mˆo.t hˆe. d¯oˆ. ng luc t` u. tra.ng th´ai n`ay sang tra.ng th´ai kh´ac v.v. Hiˆe.n nay c´o rˆa´t nhiˆ `eu phu.o.ng ph´ap dua trˆen l´ y thuyˆe´t d¯`ˆo . . thi. to˙’ ra l`a c´ac phu o ng ph´ap c´o hiˆe.u qua˙’ nhˆa´t. Chu.o.ng n`ay tr`ınh b`ay c´ac thuˆa.t to´an t`ım d¯u.`o.ng d¯i ngˇa´n nhˆa´t trˆen d¯`ˆo thi. c´o tro.ng sˆo´. 3.1 - u.` D o.ng d u.a hai d ¯i gi˜ ¯ı˙’nh 3.1.1 - u.` D o.ng d u.a hai d ¯i gi˜ ¯ı˙’nh Trong nhiˆ `eu tru.`o.ng hop, ch´ ung ta cˆ`an tra˙’ l`o.i cˆau ho˙’i: Tˆ `on ta.i d¯u.`o.ng d¯i µ t`u. d¯ı˙’nh s d¯ˆe´n . . . . d¯ı˙’nh t cu˙’a d¯`oˆ thi. c´o hu ´o ng G := (V, E)? Nˆe´u c´o, h˜ay chı˙’ ra c´ach d¯i cu˙’a d¯u `o ng d¯i µ. L`o.i gia˙’i cu˙’a b`ai to´an n`ay kh´a d¯o.n gia˙’n: ch´ `an ´ap du.ng thuˆa.t to´an t`ım kiˆe´m ung ta chı˙’ cˆ theo chiˆ `eu rˆo.ng (hoˇa.c chiˆ `eu sˆau) trˆen d¯`ˆo thi. c´o hu.´o.ng G nhu. sau. G´an mˆo˜i d¯ı˙’nh cu˙’a G mˆo.t chı˙’ sˆo´. Bˇa` ng phu.o.ng ph´ap lˇa.p, dˆ `an dˆ`an ta s˜e cho mˆo˜i d¯ı˙’nh v mˆo.t chı˙’ sˆo´ n`ao d¯o´ bˇ`a ng d¯oˆ. . . ´ d`ai d¯u `o ng d¯i ngˇan nhˆa t (sˆo cung ´ıt nhˆa´t) t` ´ ´ u. s t´o.i v. D - ´anh dˆa´u d¯ı˙’nh s bˇ`a ng chı˙’ sˆo´ 0. Nˆe´u c´ac d¯ı˙’nh d¯u o. c d¯´anh dˆa´u bˇ`a ng chı˙’ sˆo´ m lˆa.p th`anh mˆo.t tˆa.p