Luận văn Bài toán tìm đường đi ngắn nhất và ứng dụng

Tóm tắt Luận văn Bài toán tìm đường đi ngắn nhất và ứng dụng: ...tổng cỏc trọng số 1 1 ( ) w ( , ) n i i i L v và − = = ∑ Cho hai ủỉnh a, z của ủồ thị. Bài toỏn ủặt ra là tỡm ủường ủi ngắn nhất từ a ủến z. 2.1.2. Thuật toỏn Dijkstra : Thật toỏn tỡm ủường ủi ngắn nhất từ ủỉnh a ủến ủỉnh z trong ủú ủồ thị liờn thụng cú trọng số. trọng số cạnh (...ường ủi ngắn nhất từ i ủến j gồm dóy cỏc ủỉnh i , i1, i2, i3,…, ik, ik+1,…, im, j thỏa món i1= p(i,j), i2 =p(i1, j), … , ik+1 = p(ik,j), … , p(im,j) =j 2.3. Chu trỡnh Hamilton ngắn nhất: 2.3.1. Phỏt biểu bài toỏn : Cho ủồ thị cú trọng số G=(V,E). Kớ hiệu w(i,j) là trọng số của cạnh (i,...h ủồ thị sau: 17 Áp dụng thuật toỏn Floyd ủể tỡm ủường ủi ngắn nhất giữa tất cả cỏc cặp ủỉnh của ủồ thị trờn. Cụ thể ta cú ma trận khoảng cỏch ngắn nhất giữa cỏc ủỉnh là D: Đỉnh A B C D E F G A 0 24 75 117 151 142 149 B 24 0 51 93 127 118 125 C 75 51 0 42 76 67 74 D 117 93 42 0 34 ...