Bài giảng Thiết kế và đánh giá thuật toán: Đường đi ngắn nhất - TS. Lê Nguyên Khôi

Thiết Kế & Đánh Giá Thuật Toán<br /> Đường Đi Ngắn Nhất<br /> TS. Lê Nguyên Khôi<br /> Trường Đại Học Công Nghệ - ĐHQGHN<br /> <br /> Nội Dung<br /> Đường đi<br />
Tính chất đường đi ngắn nhất<br />
Đường đi ngắn nhất từ một đỉnh<br />
Thuật toán Dijkstra<br />
Đường đi ngắn nhất giữa mọi đỉnh<br />
Thuật toán Floyd–Warshall<br />
<br /> <br /> 1<br /> <br /> Đường Đi – Định Nghĩa<br />
<br /> <br /> Trong đồ thị vô hướng
= , <br />
<br /> <br />
<br /> <br />
<br /> <br /> Đường đi<br />
là dãy  các đỉnh  ,  , … , <br />
2 đỉnh liên tiếp  , <br />  được nối bởi 1 cạnh trong .<br />
 được gọi là đường đi từ  đến <br /> Chu trình<br />
là đường đi  ,  , … ,  với  > 1<br />
trong đó  đỉnh đầu tiên phân biệt và  = <br /> <br /> Với đồ thị có hướng, trong một đường đi hay<br /> chu trình, 2 đỉnh liên tiếp ( , <br />  ) phải là một<br /> cung thuộc <br /> <br /> 2<br /> <br /> Đường Đi – Trọng Số<br /> Đồ thị có hướng
= ,  với hàm trọng số<br /> cung :  → . Trọng số của đường đi<br />    →  → ⋯ →  được định nghĩa:<br /> <br /> <br />       , <br /> Ví dụ:    2<br /> <br /> <br /> <br /> 3<br /> <br /> Đường Đi Ngắn Nhất – Định Nghĩa<br /> Đường đi ngắn nhất (ĐĐNN) từ  đến  là<br /> đường đi có trọng số nhỏ nhất từ  đến .<br /> Trọng số đường đi ngắn nhất từ  đến <br /> được định nghĩa:<br /> ,  = min   :  đường đi từ  đến <br /> Chú ý: ,  = ∞ không tồn tại đường đi<br /> từ  đến .<br /> 4<br /> <br />