Lý thuyết đồ thị - Tìm đường đi ngắn nhất với Floyd
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (120.5 KB, 3 trang )
<span class='text_page_counter'>(1)</span><div class='page_container' data-page=1>
Lý thuy t đ thế ồ ị
<b>Tìm đ</b>
<b>ườ</b>
<b>ng đi ng n nh t v i Floyd</b>
<b>ắ</b>
<b>ấ ớ</b>
<b>Lý thuy t</b>
<b>ế</b>
Thu t tốn Floyd cho phép tìm đậ ường đi ng n nh t gi a hai đ nh b t kỳ trong đ th . Do đóắ ấ ữ ỉ ấ ồ ị
chi phí c a thu t tốn Floyd có th l n nh ng bù l i, ta có th t n d ng đ tính trủ ậ ể ớ ư ạ ể ậ ụ ể ước k tế
qu ch trong m t l n ch y thu t toán duy nh t.ả ỉ ộ ầ ạ ậ ấ
<b>Tìm hi u qua ví d</b>
<b>ể</b>
<b>ụ</b>
Vd: cho đ th sau:ồ ị
Ta s l p m t b ng L mô t đẽ ậ ộ ả ả ường đi ng n nh t t m t đ nh i đ n m t đ nh j nh sau:ắ ấ ừ ộ ỉ ế ộ ỉ ư
t i \ đ nừ ế
j
0 1 2 3
0 0 0 0 3
1 2 0 0 6
2 0 0 0 0
3 0 0 2 0
L u ý: các giá tr tr ng ng v i tr 0 – khơng có đư ị ố ứ ớ ị ường đi. Khi cài đ t c n xét riêng trặ ầ ường
h p giá tr 0.ợ ị
Nh n xét: ta có t 0 → 2 hi n gi ch a có đậ ừ ệ ờ ư ường đi (chi phí là 0). Ta th y ngay m tấ ộ
đường đi gián ti p t 0 → 3 r i t 3 → 2 v i chi phí là 3 + 2 = 5. C p nh t l i b ng L trên:ế ừ ồ ừ ớ ậ ậ ạ ả
<b>t i \ đ nừ</b> <b>ế</b>
<b>j</b>
<b>0</b> <b>1 2 3</b>
<b>0</b> 3
<b>1</b> 2 6
<b>2</b> 5 (qua 3)
<b>3</b> 2
M t trộ ường h p khác n a là t 1 → 3 có chi phí hi n t i là 6. Ta th y ngay m t đợ ữ ừ ệ ạ ấ ộ ường đi
gián ti p t 1 → 0 r i t 0 → 3 v i chi phí là 2 + 3 = 5 bé h n chi phí lúc đ u. C p nh tế ừ ồ ừ ớ ơ ầ ậ ậ
l i b ng L trên:ạ ả
<b>t i \ đ nừ</b> <b>ế</b>
<b>j</b> <b>0</b> <b>1 2 3</b>
<b>0</b> 3
<b>1</b> 2 6 5 (qua 0)
<b>2</b> 5 (qua 3)
<b>3</b> 2
1 Lê Th y Anhụ
0
1 2
3
2
6
3
</div>
<span class='text_page_counter'>(2)</span><div class='page_container' data-page=2>
Lý thuy t đ thế ồ ị
Cu i cùng, ta ch cịn tìm đố ỉ ược m trộ ường h p n a là t 1 → 2 ch a có đợ ữ ừ ư ường đi. Phát
hi n ra đệ ường đi t 1 → 3 r i t 3 → 2 có chi phí là 5 + 2 = 7. C p nh t l i b ng L trên:ừ ồ ừ ậ ậ ạ ả
t i \ đ nừ ế
j
0 1 2 3
0 3
1 2 7 (qua 3) 5 (qua 0)
2 5 (qua 3)
3 2
Lúc này ta khơng cịn tìm được m t c i ti n nào n a c . ộ ả ế ữ ả
N u ngế ười dùng yêu c u tìm đầ ường đi ng n nh t t 1 đ n 2, ta có th xác nh n là chi phíắ ấ ừ ế ể ậ
b ng 7. Đằ ường đi nh sau:ư
1 → 2 (có 1 → 2 đi qua 3)
1 → 3 → 2 (có 1 → 3 qua 0)
1 → 0 → 3 → 2
K t qu tìm đế ả ược là đường đi 1 → 0 → 3 → 2.
<b>L u ýư</b> : th t duy t r t quan tr ng. Gi s chúng ta tìm ra cách c i ti n theo th t sauứ ự ệ ấ ọ ả ử ả ế ứ ự
(sinh viên ki m tra l i giá tr b ng L trên gi y đ hi u rõ h n):ể ạ ị ả ấ ể ể ơ
1. 1 → 3 r i 3 → 2 thay cho 1 → 2 (chi phí là 8)ồ
2. 1 → 0 r i 0 → 3 thay cho 1 → 3 (chi phí m i là 5, cũ là 6)ồ ớ
3. <i><b>1 → 3 r i 3 → 2 thay cho 1 → 2 (chi phí m i là 7, chi phí cũ là 8).</b><b>ồ</b></i> <i><b>ớ</b></i>
4. …
khi đó ta s ph i duy t r t nhi u l n m t trẽ ả ệ ấ ề ầ ộ ường h p.ợ
<b>Tóm t t thu t toán Floyd</b>
<b>ắ</b>
<b>ậ</b>
// kh i t o L[][] b ng v i ma tr n k c a đ thở ạ ằ ớ ậ ề ủ ồ ị
…
for (i…)
for (j…)
if (L[j][i] > 0)
{
for (k…)
if (L[i][k] > 0)
if (L[j][k] == 0 || // ch a có đư ường đi t j ừ → k
L[j][k] > L[j][i]+L[i][k] // đường đi trung gian ng n h n)ắ ơ
{
L[j][k] = L[j][i]+L[i][k];
TG[j][k] = i;
}
}
2 Lê Th y Anhụ
i
</div>
<span class='text_page_counter'>(3)</span><div class='page_container' data-page=3>
Lý thuy t đ thế ồ ị
<b>L u ýư</b> : Nh đã lư ưu ý trong ví d , th t duy t r t quan tr ng, sinh viên c n l u ụ ứ ự ệ ấ ọ ầ ư th t cácứ ự
vòng for i, j, k.
<b>Cài đ t – C u trúc d li u</b>
<b>ặ</b>
<b>ấ</b>
<b>ữ ệ</b>
C n hai m ng hai chi uầ ả ề
int L[MAX][MAX]; // dùng double n u ma tr n k dùng ki u th cế ậ ề ể ự
int TG[MAX][MAX];
<b>Cài đ t – hàm Floyd</b>
<b>ặ</b>
Sinh viên t cài đ tự ặ
<b>Cài đ t – hàm PrintMinRoute</b>
<b>ặ</b>
void PrintMinRoute(nStartNode, nEndNode)
{
if (L[nStartNode][nEndNode] <= 0)
printf(“Khong co duong di…);
else {
printf(“Chi phí đường đi…”);
<i>// dị ngược l i đạ</i> <i>ường đi, b t đ u t đ nh nEndNodeắ</i> <i>ầ</i> <i>ừ</i> <i>ỉ</i>
k = nEndNode;
while (k != nStartNode) {
printf(“%d <-- ”, k);
<i>// do th t duy t, đứ</i> <i>ự</i> <i>ệ</i> <i>ường đi t nStartNode đ n kừ</i> <i>ế</i>
<i>// s có đ nh TG[nStartNode][k] n m trẽ</i> <i>ỉ</i> <i>ằ</i> <i>ước đ nh kỉ</i>
k = TG[nStartNode][k];
}
printf(“%d “, k);
}
}
<b>Cài đ t – hàm main</b>
<b>ặ</b>
void main()
{
Nhap_Ma_Tran_Ke();
Floyd(); <i>// ta ch ch y Floyd m t l n cho m t đ thỉ</i> <i>ạ</i> <i>ộ</i> <i>ầ</i> <i>ộ</i> <i>ồ</i> <i>ị</i>
do {
<i>// và có th tìm nhi u để</i> <i>ề</i> <i>ường đi khác nhau</i>
Nhap_Dinh_XuatPhat_KetThuc();
PrintMinRoute(nStartNode, nEndNode);
while (Nguoi_Dung_Muon_Chay_Tiep);
}
</div>
<!--links-->
