tailieunhanh - Đồ 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 3 C´ ac b` ai to´ an vˆ ¯u.` `e d d ¯i Trong c´ac u ´.ng thuc tˆe´, ta cˆ`an t`ım d¯u.` d¯i (nˆe´u c´o) gi˜ hai d¯ı˙’nh cu˙’a d¯`oˆ thi D - . . , 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 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 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 nhˆa´t (theo tiˆeu chuˆa˙’n khoa˙’ng c´ach, th` gian chi ph´ı) trˆen ba˙’n d¯`oˆ giao thˆong; b`ai to´an ph´ap tiˆe´t nhˆa´t d¯ˆe˙’ d¯ hˆe. d¯oˆ. ng luc t` u. th´ai n`ay sang th´ai kh´ac . nay c´o rˆa´t nhiˆ `eu 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 qua˙’ nhˆa´t. n`ay tr`ınh b`ay c´ac to´an t`ım d¯u.` d¯i ngˇa´n nhˆa´t trˆen d¯`ˆo thi. c´o sˆo´. - u.` D d hai d ¯i gi˜ ¯ı˙’nh - u.` D d hai d ¯i gi˜ ¯ı˙’nh Trong nhiˆ `eu tru.` hop, ch´ ung ta cˆ`an tra˙’ l` cˆau ho˙’i: Tˆ `on d¯u.` 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` gia˙’i cu˙’a b`ai to´an n`ay kh´a d¯ gia˙’n: ch´ `an ´ap to´an t`ım kiˆe´m ung ta chı˙’ cˆ theo chiˆ `eu ( chiˆ `eu sˆau) trˆen d¯`ˆo thi. c´o hu.´ G nhu. sau. G´an mˆo˜i d¯ı˙’nh cu˙’a G chı˙’ sˆo´. Bˇa` ng ph´ap , dˆ `an dˆ`an ta s˜e cho mˆo˜i d¯ı˙’nh v 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´ 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 th`anh