Thuật toán Floyd-Warshall dùng để giải quyết bài toán đường đi ngắn nhất mọi cặp đỉnh (All-pairs shortest path), đồ thị có thể có trọng số âm.
Cho đồ thị gồm N đỉnh và một ma trận trọng số W, trong đó ô (i,j) cho biết rằng có một đường đi trực tiếp từ i→j với trọng số là Wi,j. Yêu cầu tìm đường đi ngắn nhất giữa mọi cặp đỉnh trên đồ thị.
Về lý thuyết là như nhau nên Tui không có trình bày lại. Các bạn có thể đọc tại link Tiếng Việt https://vnoi.info/wiki/algo/graph-theory/shortest-path.md#3-thu%E1%BA%ADt-to%C3%A1n-floyd-warshall hoặc link Tiếng Anh https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
Bài viết này Tui có viết 1 phần mềm giải chi tiết từng bước đường đi ngắn nhất qua mọi cặp đỉnh dùng giải thuật Floyd-Warshll. Từ phần mềm bạn có thể học được cách tìm đường đi ngắn nhất. Phần mềm exe và mã nguồn ở cuối bài viết.
Tui viết lại mã giả của giải thuật:
Input: Mảng D 2 chiều, trong đó D [i, j] = trọng số của đường đi từ (i, j), nếu không có đường đi trực tiếp từ (i, j) D [i, j] = ∞, khởi tạo với mọi D [i, i] = 0..
Output: Mảng 2 chiều D lưu trữ khoảng cách của tất cả các cặp đường đi ngắn nhất
1. for k = 0 to n-1
2. for i = 0 to n -1 ( i≠k)
3. for j = 0 to n -1 (j≠k, j≠i)
4. D[i,j] = min{D[i,k]+D[k,j], D[i,j]}
Ví dụ 1 : cho đồ thị có hướng và các trọng số như dưới đây, làm thế nào để tìm được đường đi ngắn nhất qua mọi cặp đỉnh:
Trước tiên ta khởi tạo bảng ban đâu theo quy tắc:
- dòng 0 là tập hợp các đỉnh trong đồ thị (đỉnh 1-> đỉnh 5)
- cột 0 là tập hợp các đỉnh trong đồ thị (đỉnh 1-> đỉnh 5)
- giá trị tại các ô [i, j] chính là trọng số từ i -> j. Nếu không có đường đi đến trực tiếp thì để ∞
Như vậy ta Khởi tạo bảng dữ liệu ban đầu như dưới đây:
| D | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 4 | 2 | 5 | ∞ |
| 2 | ∞ | 0 | 1 | ∞ | 4 |
| 3 | 1 | 3 | 0 | 1 | 2 |
| 4 | -2 | ∞ | ∞ | 0 | 2 |
| 5 | ∞ | -3 | 3 | 1 | 0 |
Tiến hành chạy từng bước giải thuật:
Khi K =0:
D[1,2] = min{D[1,0]+D[0,2], D[1,2]}=min{∞+2,1}=1
D[1,3] = min{D[1,0]+D[0,3], D[1,3]}=min{∞+5,∞}=∞
D[1,4] = min{D[1,0]+D[0,4], D[1,4]}=min{∞+∞,4}=4
D[2,1] = min{D[2,0]+D[0,1], D[2,1]}=min{1+4,3}=3
D[2,3] = min{D[2,0]+D[0,3], D[2,3]}=min{1+5,1}=1
D[2,4] = min{D[2,0]+D[0,4], D[2,4]}=min{1+∞,2}=2
D[3,1] = min{D[3,0]+D[0,1], D[3,1]}=min{-2+4,∞}=2
=>Vì trong bảng trước, D[3,1]=∞ > 2
=>Nên Chúng ta cập nhật D[3,1]=2
Bảng sau khi cập nhật D[3,1]:
| D | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 4 | 2 | 5 | ∞ |
| 2 | ∞ | 0 | 1 | ∞ | 4 |
| 3 | 1 | 3 | 0 | 1 | 2 |
| 4 | -2 | 2 | ∞ | 0 | 2 |
| 5 | ∞ | -3 | 3 | 1 | 0 |
D[3,2] = min{D[3,0]+D[0,2], D[3,2]}=min{-2+2,∞}=0
=>Vì trong bảng trước, D[3,2]=∞ > 0
=>Nên Chúng ta cập nhật D[3,2]=0
Bảng sau khi cập nhật D[3,2]:
| D | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 4 | 2 | 5 | ∞ |
| 2 | ∞ | 0 | 1 | ∞ | 4 |
| 3 | 1 | 3 | 0 | 1 | 2 |
| 4 | -2 | 2 | 0 | 0 | 2 |
| 5 | ∞ | -3 | 3 | 1 | 0 |
D[3,4] = min{D[3,0]+D[0,4], D[3,4]}=min{-2+∞,2}=2
D[4,1] = min{D[4,0]+D[0,1], D[4,1]}=min{∞+4,-3}=-3
D[4,2] = min{D[4,0]+D[0,2], D[4,2]}=min{∞+2,3}=3
D[4,3] = min{D[4,0]+D[0,3], D[4,3]}=min{∞+5,1}=1
Khi K =1:
D[0,2] = min{D[0,1]+D[1,2], D[0,2]}=min{4+1,2}=2
D[0,3] = min{D[0,1]+D[1,3], D[0,3]}=min{4+∞,5}=5
D[0,4] = min{D[0,1]+D[1,4], D[0,4]}=min{4+4,∞}=8
=>Vì trong bảng trước, D[0,4]=∞ > 8
=>Nên Chúng ta cập nhật D[0,4]=8
Bảng sau khi cập nhật D[0,4]:
| D | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 4 | 2 | 5 | 8 |
| 2 | ∞ | 0 | 1 | ∞ | 4 |
| 3 | 1 | 3 | 0 | 1 | 2 |
| 4 | -2 | 2 | 0 | 0 | 2 |
| 5 | ∞ | -3 | 3 | 1 | 0 |
D[2,0] = min{D[2,1]+D[1,0], D[2,0]}=min{3+∞,1}=1
D[2,3] = min{D[2,1]+D[1,3], D[2,3]}=min{3+∞,1}=1
D[2,4] = min{D[2,1]+D[1,4], D[2,4]}=min{3+4,2}=2
D[3,0] = min{D[3,1]+D[1,0], D[3,0]}=min{2+∞,-2}=-2
D[3,2] = min{D[3,1]+D[1,2], D[3,2]}=min{2+1,0}=0
D[3,4] = min{D[3,1]+D[1,4], D[3,4]}=min{2+4,2}=2
D[4,0] = min{D[4,1]+D[1,0], D[4,0]}=min{-3+∞,∞}=∞
D[4,2] = min{D[4,1]+D[1,2], D[4,2]}=min{-3+1,3}=-2
=>Vì trong bảng trước, D[4,2]=3 > -2
=>Nên Chúng ta cập nhật D[4,2]=-2
Bảng sau khi cập nhật D[4,2]:
| D | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 4 | 2 | 5 | 8 |
| 2 | ∞ | 0 | 1 | ∞ | 4 |
| 3 | 1 | 3 | 0 | 1 | 2 |
| 4 | -2 | 2 | 0 | 0 | 2 |
| 5 | ∞ | -3 | -2 | 1 | 0 |
D[4,3] = min{D[4,1]+D[1,3], D[4,3]}=min{-3+∞,1}=1
Khi K =2:
D[0,1] = min{D[0,2]+D[2,1], D[0,1]}=min{2+3,4}=4
D[0,3] = min{D[0,2]+D[2,3], D[0,3]}=min{2+1,5}=3
=>Vì trong bảng trước, D[0,3]=5 > 3
=>Nên Chúng ta cập nhật D[0,3]=3
Bảng sau khi cập nhật D[0,3]:
| D | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 4 | 2 | 3 | 8 |
| 2 | ∞ | 0 | 1 | ∞ | 4 |
| 3 | 1 | 3 | 0 | 1 | 2 |
| 4 | -2 | 2 | 0 | 0 | 2 |
| 5 | ∞ | -3 | -2 | 1 | 0 |
D[0,4] = min{D[0,2]+D[2,4], D[0,4]}=min{2+2,8}=4
=>Vì trong bảng trước, D[0,4]=8 > 4
=>Nên Chúng ta cập nhật D[0,4]=4
Bảng sau khi cập nhật D[0,4]:
| D | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 4 | 2 | 3 | 4 |
| 2 | ∞ | 0 | 1 | ∞ | 4 |
| 3 | 1 | 3 | 0 | 1 | 2 |
| 4 | -2 | 2 | 0 | 0 | 2 |
| 5 | ∞ | -3 | -2 | 1 | 0 |
D[1,0] = min{D[1,2]+D[2,0], D[1,0]}=min{1+1,∞}=2
=>Vì trong bảng trước, D[1,0]=∞ > 2
=>Nên Chúng ta cập nhật D[1,0]=2
Bảng sau khi cập nhật D[1,0]:
| D | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 4 | 2 | 3 | 4 |
| 2 | 2 | 0 | 1 | ∞ | 4 |
| 3 | 1 | 3 | 0 | 1 | 2 |
| 4 | -2 | 2 | 0 | 0 | 2 |
| 5 | ∞ | -3 | -2 | 1 | 0 |
D[1,3] = min{D[1,2]+D[2,3], D[1,3]}=min{1+1,∞}=2
=>Vì trong bảng trước, D[1,3]=∞ > 2
=>Nên Chúng ta cập nhật D[1,3]=2
Bảng sau khi cập nhật D[1,3]:
| D | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 4 | 2 | 3 | 4 |
| 2 | 2 | 0 | 1 | 2 | 4 |
| 3 | 1 | 3 | 0 | 1 | 2 |
| 4 | -2 | 2 | 0 | 0 | 2 |
| 5 | ∞ | -3 | -2 | 1 | 0 |
D[1,4] = min{D[1,2]+D[2,4], D[1,4]}=min{1+2,4}=3
=>Vì trong bảng trước, D[1,4]=4 > 3
=>Nên Chúng ta cập nhật D[1,4]=3
Bảng sau khi cập nhật D[1,4]:
| D | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 4 | 2 | 3 | 4 |
| 2 | 2 | 0 | 1 | 2 | 3 |
| 3 | 1 | 3 | 0 | 1 | 2 |
| 4 | -2 | 2 | 0 | 0 | 2 |
| 5 | ∞ | -3 | -2 | 1 | 0 |
D[3,0] = min{D[3,2]+D[2,0], D[3,0]}=min{0+1,-2}=-2
D[3,1] = min{D[3,2]+D[2,1], D[3,1]}=min{0+3,2}=2
D[3,4] = min{D[3,2]+D[2,4], D[3,4]}=min{0+2,2}=2
D[4,0] = min{D[4,2]+D[2,0], D[4,0]}=min{-2+1,∞}=-1
=>Vì trong bảng trước, D[4,0]=∞ > -1
=>Nên Chúng ta cập nhật D[4,0]=-1
Bảng sau khi cập nhật D[4,0]:
| D | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 4 | 2 | 3 | 4 |
| 2 | 2 | 0 | 1 | 2 | 3 |
| 3 | 1 | 3 | 0 | 1 | 2 |
| 4 | -2 | 2 | 0 | 0 | 2 |
| 5 | -1 | -3 | -2 | 1 | 0 |
D[4,1] = min{D[4,2]+D[2,1], D[4,1]}=min{-2+3,-3}=-3
D[4,3] = min{D[4,2]+D[2,3], D[4,3]}=min{-2+1,1}=-1
=>Vì trong bảng trước, D[4,3]=1 > -1
=>Nên Chúng ta cập nhật D[4,3]=-1
Bảng sau khi cập nhật D[4,3]:
| D | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 4 | 2 | 3 | 4 |
| 2 | 2 | 0 | 1 | 2 | 3 |
| 3 | 1 | 3 | 0 | 1 | 2 |
| 4 | -2 | 2 | 0 | 0 | 2 |
| 5 | -1 | -3 | -2 | -1 | 0 |
Khi K =3:
D[0,1] = min{D[0,3]+D[3,1], D[0,1]}=min{3+2,4}=4
D[0,2] = min{D[0,3]+D[3,2], D[0,2]}=min{3+0,2}=2
D[0,4] = min{D[0,3]+D[3,4], D[0,4]}=min{3+2,4}=4
D[1,0] = min{D[1,3]+D[3,0], D[1,0]}=min{2+-2,2}=0
=>Vì trong bảng trước, D[1,0]=2 > 0
=>Nên Chúng ta cập nhật D[1,0]=0
Bảng sau khi cập nhật D[1,0]:
| D | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 4 | 2 | 3 | 4 |
| 2 | 0 | 0 | 1 | 2 | 3 |
| 3 | 1 | 3 | 0 | 1 | 2 |
| 4 | -2 | 2 | 0 | 0 | 2 |
| 5 | -1 | -3 | -2 | -1 | 0 |
D[1,2] = min{D[1,3]+D[3,2], D[1,2]}=min{2+0,1}=1
D[1,4] = min{D[1,3]+D[3,4], D[1,4]}=min{2+2,3}=3
D[2,0] = min{D[2,3]+D[3,0], D[2,0]}=min{1+-2,1}=-1
=>Vì trong bảng trước, D[2,0]=1 > -1
=>Nên Chúng ta cập nhật D[2,0]=-1
Bảng sau khi cập nhật D[2,0]:
| D | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 4 | 2 | 3 | 4 |
| 2 | 0 | 0 | 1 | 2 | 3 |
| 3 | -1 | 3 | 0 | 1 | 2 |
| 4 | -2 | 2 | 0 | 0 | 2 |
| 5 | -1 | -3 | -2 | -1 | 0 |
D[2,1] = min{D[2,3]+D[3,1], D[2,1]}=min{1+2,3}=3
D[2,4] = min{D[2,3]+D[3,4], D[2,4]}=min{1+2,2}=2
D[4,0] = min{D[4,3]+D[3,0], D[4,0]}=min{-1+-2,-1}=-3
=>Vì trong bảng trước, D[4,0]=-1 > -3
=>Nên Chúng ta cập nhật D[4,0]=-3
Bảng sau khi cập nhật D[4,0]:
| D | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 4 | 2 | 3 | 4 |
| 2 | 0 | 0 | 1 | 2 | 3 |
| 3 | -1 | 3 | 0 | 1 | 2 |
| 4 | -2 | 2 | 0 | 0 | 2 |
| 5 | -3 | -3 | -2 | -1 | 0 |
D[4,1] = min{D[4,3]+D[3,1], D[4,1]}=min{-1+2,-3}=-3
D[4,2] = min{D[4,3]+D[3,2], D[4,2]}=min{-1+0,-2}=-2
Khi K =4:
D[0,1] = min{D[0,4]+D[4,1], D[0,1]}=min{4+-3,4}=1
=>Vì trong bảng trước, D[0,1]=4 > 1
=>Nên Chúng ta cập nhật D[0,1]=1
Bảng sau khi cập nhật D[0,1]:
| D | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 1 | 2 | 3 | 4 |
| 2 | 0 | 0 | 1 | 2 | 3 |
| 3 | -1 | 3 | 0 | 1 | 2 |
| 4 | -2 | 2 | 0 | 0 | 2 |
| 5 | -3 | -3 | -2 | -1 | 0 |
D[0,2] = min{D[0,4]+D[4,2], D[0,2]}=min{4+-2,2}=2
D[0,3] = min{D[0,4]+D[4,3], D[0,3]}=min{4+-1,3}=3
D[1,0] = min{D[1,4]+D[4,0], D[1,0]}=min{3+-3,0}=0
D[1,2] = min{D[1,4]+D[4,2], D[1,2]}=min{3+-2,1}=1
D[1,3] = min{D[1,4]+D[4,3], D[1,3]}=min{3+-1,2}=2
D[2,0] = min{D[2,4]+D[4,0], D[2,0]}=min{2+-3,-1}=-1
D[2,1] = min{D[2,4]+D[4,1], D[2,1]}=min{2+-3,3}=-1
=>Vì trong bảng trước, D[2,1]=3 > -1
=>Nên Chúng ta cập nhật D[2,1]=-1
Bảng sau khi cập nhật D[2,1]:
| D | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 1 | 2 | 3 | 4 |
| 2 | 0 | 0 | 1 | 2 | 3 |
| 3 | -1 | -1 | 0 | 1 | 2 |
| 4 | -2 | 2 | 0 | 0 | 2 |
| 5 | -3 | -3 | -2 | -1 | 0 |
D[2,3] = min{D[2,4]+D[4,3], D[2,3]}=min{2+-1,1}=1
D[3,0] = min{D[3,4]+D[4,0], D[3,0]}=min{2+-3,-2}=-2
D[3,1] = min{D[3,4]+D[4,1], D[3,1]}=min{2+-3,2}=-1
=>Vì trong bảng trước, D[3,1]=2 > -1
=>Nên Chúng ta cập nhật D[3,1]=-1
Bảng sau khi cập nhật D[3,1]:
| D | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 1 | 2 | 3 | 4 |
| 2 | 0 | 0 | 1 | 2 | 3 |
| 3 | -1 | -1 | 0 | 1 | 2 |
| 4 | -2 | -1 | 0 | 0 | 2 |
| 5 | -3 | -3 | -2 | -1 | 0 |
D[3,2] = min{D[3,4]+D[4,2], D[3,2]}=min{2+-2,0}=0
Cuối cùng chúng ta có bảng kết quả lưu đường đi ngắn nhất qua mọi cặp đỉnh:
| D | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 1 | 2 | 3 | 4 |
| 2 | 0 | 0 | 1 | 2 | 3 |
| 3 | -1 | -1 | 0 | 1 | 2 |
| 4 | -2 | -1 | 0 | 0 | 2 |
| 5 | -3 | -3 | -2 | -1 | 0 |
Ví dụ 2:
Cho đồ thị có hướng và các trọng số như dưới đây, làm thế nào để tìm được đường đi ngắn nhất qua mọi cặp đỉnh:
Tương tự như ví dụ 1, ta tạo bảng ban đầu như sau:
Khởi tạo bảng dữ liệu ban đầu:
| D | a | b | c | d | e | f | g | h |
| a | 0 | 4 | ∞ | 2 | 7 | ∞ | ∞ | ∞ |
| b | ∞ | 0 | ∞ | ∞ | 2 | ∞ | ∞ | ∞ |
| c | ∞ | ∞ | 0 | ∞ | 4 | ∞ | ∞ | ∞ |
| d | ∞ | ∞ | ∞ | 0 | ∞ | ∞ | 1 | 4 |
| e | ∞ | ∞ | ∞ | ∞ | 0 | 2 | ∞ | ∞ |
| f | ∞ | ∞ | 1 | ∞ | ∞ | 0 | ∞ | ∞ |
| g | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 | 2 |
| h | ∞ | ∞ | ∞ | ∞ | 5 | 1 | ∞ | 0 |
Khi K =0:
D[1,2] = min{D[1,0]+D[0,2], D[1,2]}=min{∞+∞,∞}=∞
D[1,3] = min{D[1,0]+D[0,3], D[1,3]}=min{∞+2,∞}=∞
D[1,4] = min{D[1,0]+D[0,4], D[1,4]}=min{∞+7,2}=2
D[1,5] = min{D[1,0]+D[0,5], D[1,5]}=min{∞+∞,∞}=∞
D[1,6] = min{D[1,0]+D[0,6], D[1,6]}=min{∞+∞,∞}=∞
D[1,7] = min{D[1,0]+D[0,7], D[1,7]}=min{∞+∞,∞}=∞
D[2,1] = min{D[2,0]+D[0,1], D[2,1]}=min{∞+4,∞}=∞
D[2,3] = min{D[2,0]+D[0,3], D[2,3]}=min{∞+2,∞}=∞
D[2,4] = min{D[2,0]+D[0,4], D[2,4]}=min{∞+7,4}=4
D[2,5] = min{D[2,0]+D[0,5], D[2,5]}=min{∞+∞,∞}=∞
D[2,6] = min{D[2,0]+D[0,6], D[2,6]}=min{∞+∞,∞}=∞
D[2,7] = min{D[2,0]+D[0,7], D[2,7]}=min{∞+∞,∞}=∞
D[3,1] = min{D[3,0]+D[0,1], D[3,1]}=min{∞+4,∞}=∞
D[3,2] = min{D[3,0]+D[0,2], D[3,2]}=min{∞+∞,∞}=∞
D[3,4] = min{D[3,0]+D[0,4], D[3,4]}=min{∞+7,∞}=∞
D[3,5] = min{D[3,0]+D[0,5], D[3,5]}=min{∞+∞,∞}=∞
D[3,6] = min{D[3,0]+D[0,6], D[3,6]}=min{∞+∞,1}=1
D[3,7] = min{D[3,0]+D[0,7], D[3,7]}=min{∞+∞,4}=4
D[4,1] = min{D[4,0]+D[0,1], D[4,1]}=min{∞+4,∞}=∞
D[4,2] = min{D[4,0]+D[0,2], D[4,2]}=min{∞+∞,∞}=∞
D[4,3] = min{D[4,0]+D[0,3], D[4,3]}=min{∞+2,∞}=∞
D[4,5] = min{D[4,0]+D[0,5], D[4,5]}=min{∞+∞,2}=2
D[4,6] = min{D[4,0]+D[0,6], D[4,6]}=min{∞+∞,∞}=∞
D[4,7] = min{D[4,0]+D[0,7], D[4,7]}=min{∞+∞,∞}=∞
D[5,1] = min{D[5,0]+D[0,1], D[5,1]}=min{∞+4,∞}=∞
D[5,2] = min{D[5,0]+D[0,2], D[5,2]}=min{∞+∞,1}=1
D[5,3] = min{D[5,0]+D[0,3], D[5,3]}=min{∞+2,∞}=∞
D[5,4] = min{D[5,0]+D[0,4], D[5,4]}=min{∞+7,∞}=∞
D[5,6] = min{D[5,0]+D[0,6], D[5,6]}=min{∞+∞,∞}=∞
D[5,7] = min{D[5,0]+D[0,7], D[5,7]}=min{∞+∞,∞}=∞
D[6,1] = min{D[6,0]+D[0,1], D[6,1]}=min{∞+4,∞}=∞
D[6,2] = min{D[6,0]+D[0,2], D[6,2]}=min{∞+∞,∞}=∞
D[6,3] = min{D[6,0]+D[0,3], D[6,3]}=min{∞+2,∞}=∞
D[6,4] = min{D[6,0]+D[0,4], D[6,4]}=min{∞+7,∞}=∞
D[6,5] = min{D[6,0]+D[0,5], D[6,5]}=min{∞+∞,∞}=∞
D[6,7] = min{D[6,0]+D[0,7], D[6,7]}=min{∞+∞,2}=2
D[7,1] = min{D[7,0]+D[0,1], D[7,1]}=min{∞+4,∞}=∞
D[7,2] = min{D[7,0]+D[0,2], D[7,2]}=min{∞+∞,∞}=∞
D[7,3] = min{D[7,0]+D[0,3], D[7,3]}=min{∞+2,∞}=∞
D[7,4] = min{D[7,0]+D[0,4], D[7,4]}=min{∞+7,5}=5
D[7,5] = min{D[7,0]+D[0,5], D[7,5]}=min{∞+∞,1}=1
D[7,6] = min{D[7,0]+D[0,6], D[7,6]}=min{∞+∞,∞}=∞
Khi K =1:
D[0,2] = min{D[0,1]+D[1,2], D[0,2]}=min{4+∞,∞}=∞
D[0,3] = min{D[0,1]+D[1,3], D[0,3]}=min{4+∞,2}=2
D[0,4] = min{D[0,1]+D[1,4], D[0,4]}=min{4+2,7}=6
=>Vì trong bảng trước, D[0,4]=7 > 6
=>Nên Chúng ta cập nhật D[0,4]=6
Bảng sau khi cập nhật D[0,4]:
| D | a | b | c | d | e | f | g | h |
| a | 0 | 4 | ∞ | 2 | 6 | ∞ | ∞ | ∞ |
| b | ∞ | 0 | ∞ | ∞ | 2 | ∞ | ∞ | ∞ |
| c | ∞ | ∞ | 0 | ∞ | 4 | ∞ | ∞ | ∞ |
| d | ∞ | ∞ | ∞ | 0 | ∞ | ∞ | 1 | 4 |
| e | ∞ | ∞ | ∞ | ∞ | 0 | 2 | ∞ | ∞ |
| f | ∞ | ∞ | 1 | ∞ | ∞ | 0 | ∞ | ∞ |
| g | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 | 2 |
| h | ∞ | ∞ | ∞ | ∞ | 5 | 1 | ∞ | 0 |
D[0,5] = min{D[0,1]+D[1,5], D[0,5]}=min{4+∞,∞}=∞
D[0,6] = min{D[0,1]+D[1,6], D[0,6]}=min{4+∞,∞}=∞
D[0,7] = min{D[0,1]+D[1,7], D[0,7]}=min{4+∞,∞}=∞
D[2,0] = min{D[2,1]+D[1,0], D[2,0]}=min{∞+∞,∞}=∞
D[2,3] = min{D[2,1]+D[1,3], D[2,3]}=min{∞+∞,∞}=∞
D[2,4] = min{D[2,1]+D[1,4], D[2,4]}=min{∞+2,4}=4
D[2,5] = min{D[2,1]+D[1,5], D[2,5]}=min{∞+∞,∞}=∞
D[2,6] = min{D[2,1]+D[1,6], D[2,6]}=min{∞+∞,∞}=∞
D[2,7] = min{D[2,1]+D[1,7], D[2,7]}=min{∞+∞,∞}=∞
D[3,0] = min{D[3,1]+D[1,0], D[3,0]}=min{∞+∞,∞}=∞
D[3,2] = min{D[3,1]+D[1,2], D[3,2]}=min{∞+∞,∞}=∞
D[3,4] = min{D[3,1]+D[1,4], D[3,4]}=min{∞+2,∞}=∞
D[3,5] = min{D[3,1]+D[1,5], D[3,5]}=min{∞+∞,∞}=∞
D[3,6] = min{D[3,1]+D[1,6], D[3,6]}=min{∞+∞,1}=1
D[3,7] = min{D[3,1]+D[1,7], D[3,7]}=min{∞+∞,4}=4
D[4,0] = min{D[4,1]+D[1,0], D[4,0]}=min{∞+∞,∞}=∞
D[4,2] = min{D[4,1]+D[1,2], D[4,2]}=min{∞+∞,∞}=∞
D[4,3] = min{D[4,1]+D[1,3], D[4,3]}=min{∞+∞,∞}=∞
D[4,5] = min{D[4,1]+D[1,5], D[4,5]}=min{∞+∞,2}=2
D[4,6] = min{D[4,1]+D[1,6], D[4,6]}=min{∞+∞,∞}=∞
D[4,7] = min{D[4,1]+D[1,7], D[4,7]}=min{∞+∞,∞}=∞
D[5,0] = min{D[5,1]+D[1,0], D[5,0]}=min{∞+∞,∞}=∞
D[5,2] = min{D[5,1]+D[1,2], D[5,2]}=min{∞+∞,1}=1
D[5,3] = min{D[5,1]+D[1,3], D[5,3]}=min{∞+∞,∞}=∞
D[5,4] = min{D[5,1]+D[1,4], D[5,4]}=min{∞+2,∞}=∞
D[5,6] = min{D[5,1]+D[1,6], D[5,6]}=min{∞+∞,∞}=∞
D[5,7] = min{D[5,1]+D[1,7], D[5,7]}=min{∞+∞,∞}=∞
D[6,0] = min{D[6,1]+D[1,0], D[6,0]}=min{∞+∞,∞}=∞
D[6,2] = min{D[6,1]+D[1,2], D[6,2]}=min{∞+∞,∞}=∞
D[6,3] = min{D[6,1]+D[1,3], D[6,3]}=min{∞+∞,∞}=∞
D[6,4] = min{D[6,1]+D[1,4], D[6,4]}=min{∞+2,∞}=∞
D[6,5] = min{D[6,1]+D[1,5], D[6,5]}=min{∞+∞,∞}=∞
D[6,7] = min{D[6,1]+D[1,7], D[6,7]}=min{∞+∞,2}=2
D[7,0] = min{D[7,1]+D[1,0], D[7,0]}=min{∞+∞,∞}=∞
D[7,2] = min{D[7,1]+D[1,2], D[7,2]}=min{∞+∞,∞}=∞
D[7,3] = min{D[7,1]+D[1,3], D[7,3]}=min{∞+∞,∞}=∞
D[7,4] = min{D[7,1]+D[1,4], D[7,4]}=min{∞+2,5}=5
D[7,5] = min{D[7,1]+D[1,5], D[7,5]}=min{∞+∞,1}=1
D[7,6] = min{D[7,1]+D[1,6], D[7,6]}=min{∞+∞,∞}=∞
Khi K =2:
D[0,1] = min{D[0,2]+D[2,1], D[0,1]}=min{∞+∞,4}=4
D[0,3] = min{D[0,2]+D[2,3], D[0,3]}=min{∞+∞,2}=2
D[0,4] = min{D[0,2]+D[2,4], D[0,4]}=min{∞+4,6}=6
D[0,5] = min{D[0,2]+D[2,5], D[0,5]}=min{∞+∞,∞}=∞
D[0,6] = min{D[0,2]+D[2,6], D[0,6]}=min{∞+∞,∞}=∞
D[0,7] = min{D[0,2]+D[2,7], D[0,7]}=min{∞+∞,∞}=∞
D[1,0] = min{D[1,2]+D[2,0], D[1,0]}=min{∞+∞,∞}=∞
D[1,3] = min{D[1,2]+D[2,3], D[1,3]}=min{∞+∞,∞}=∞
D[1,4] = min{D[1,2]+D[2,4], D[1,4]}=min{∞+4,2}=2
D[1,5] = min{D[1,2]+D[2,5], D[1,5]}=min{∞+∞,∞}=∞
D[1,6] = min{D[1,2]+D[2,6], D[1,6]}=min{∞+∞,∞}=∞
D[1,7] = min{D[1,2]+D[2,7], D[1,7]}=min{∞+∞,∞}=∞
D[3,0] = min{D[3,2]+D[2,0], D[3,0]}=min{∞+∞,∞}=∞
D[3,1] = min{D[3,2]+D[2,1], D[3,1]}=min{∞+∞,∞}=∞
D[3,4] = min{D[3,2]+D[2,4], D[3,4]}=min{∞+4,∞}=∞
D[3,5] = min{D[3,2]+D[2,5], D[3,5]}=min{∞+∞,∞}=∞
D[3,6] = min{D[3,2]+D[2,6], D[3,6]}=min{∞+∞,1}=1
D[3,7] = min{D[3,2]+D[2,7], D[3,7]}=min{∞+∞,4}=4
D[4,0] = min{D[4,2]+D[2,0], D[4,0]}=min{∞+∞,∞}=∞
D[4,1] = min{D[4,2]+D[2,1], D[4,1]}=min{∞+∞,∞}=∞
D[4,3] = min{D[4,2]+D[2,3], D[4,3]}=min{∞+∞,∞}=∞
D[4,5] = min{D[4,2]+D[2,5], D[4,5]}=min{∞+∞,2}=2
D[4,6] = min{D[4,2]+D[2,6], D[4,6]}=min{∞+∞,∞}=∞
D[4,7] = min{D[4,2]+D[2,7], D[4,7]}=min{∞+∞,∞}=∞
D[5,0] = min{D[5,2]+D[2,0], D[5,0]}=min{1+∞,∞}=∞
D[5,1] = min{D[5,2]+D[2,1], D[5,1]}=min{1+∞,∞}=∞
D[5,3] = min{D[5,2]+D[2,3], D[5,3]}=min{1+∞,∞}=∞
D[5,4] = min{D[5,2]+D[2,4], D[5,4]}=min{1+4,∞}=5
=>Vì trong bảng trước, D[5,4]=∞ > 5
=>Nên Chúng ta cập nhật D[5,4]=5
Bảng sau khi cập nhật D[5,4]:
| D | a | b | c | d | e | f | g | h |
| a | 0 | 4 | ∞ | 2 | 6 | ∞ | ∞ | ∞ |
| b | ∞ | 0 | ∞ | ∞ | 2 | ∞ | ∞ | ∞ |
| c | ∞ | ∞ | 0 | ∞ | 4 | ∞ | ∞ | ∞ |
| d | ∞ | ∞ | ∞ | 0 | ∞ | ∞ | 1 | 4 |
| e | ∞ | ∞ | ∞ | ∞ | 0 | 2 | ∞ | ∞ |
| f | ∞ | ∞ | 1 | ∞ | 5 | 0 | ∞ | ∞ |
| g | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 | 2 |
| h | ∞ | ∞ | ∞ | ∞ | 5 | 1 | ∞ | 0 |
D[5,6] = min{D[5,2]+D[2,6], D[5,6]}=min{1+∞,∞}=∞
D[5,7] = min{D[5,2]+D[2,7], D[5,7]}=min{1+∞,∞}=∞
D[6,0] = min{D[6,2]+D[2,0], D[6,0]}=min{∞+∞,∞}=∞
D[6,1] = min{D[6,2]+D[2,1], D[6,1]}=min{∞+∞,∞}=∞
D[6,3] = min{D[6,2]+D[2,3], D[6,3]}=min{∞+∞,∞}=∞
D[6,4] = min{D[6,2]+D[2,4], D[6,4]}=min{∞+4,∞}=∞
D[6,5] = min{D[6,2]+D[2,5], D[6,5]}=min{∞+∞,∞}=∞
D[6,7] = min{D[6,2]+D[2,7], D[6,7]}=min{∞+∞,2}=2
D[7,0] = min{D[7,2]+D[2,0], D[7,0]}=min{∞+∞,∞}=∞
D[7,1] = min{D[7,2]+D[2,1], D[7,1]}=min{∞+∞,∞}=∞
D[7,3] = min{D[7,2]+D[2,3], D[7,3]}=min{∞+∞,∞}=∞
D[7,4] = min{D[7,2]+D[2,4], D[7,4]}=min{∞+4,5}=5
D[7,5] = min{D[7,2]+D[2,5], D[7,5]}=min{∞+∞,1}=1
D[7,6] = min{D[7,2]+D[2,6], D[7,6]}=min{∞+∞,∞}=∞
Khi K =3:
D[0,1] = min{D[0,3]+D[3,1], D[0,1]}=min{2+∞,4}=4
D[0,2] = min{D[0,3]+D[3,2], D[0,2]}=min{2+∞,∞}=∞
D[0,4] = min{D[0,3]+D[3,4], D[0,4]}=min{2+∞,6}=6
D[0,5] = min{D[0,3]+D[3,5], D[0,5]}=min{2+∞,∞}=∞
D[0,6] = min{D[0,3]+D[3,6], D[0,6]}=min{2+1,∞}=3
=>Vì trong bảng trước, D[0,6]=∞ > 3
=>Nên Chúng ta cập nhật D[0,6]=3
Bảng sau khi cập nhật D[0,6]:
| D | a | b | c | d | e | f | g | h |
| a | 0 | 4 | ∞ | 2 | 6 | ∞ | 3 | ∞ |
| b | ∞ | 0 | ∞ | ∞ | 2 | ∞ | ∞ | ∞ |
| c | ∞ | ∞ | 0 | ∞ | 4 | ∞ | ∞ | ∞ |
| d | ∞ | ∞ | ∞ | 0 | ∞ | ∞ | 1 | 4 |
| e | ∞ | ∞ | ∞ | ∞ | 0 | 2 | ∞ | ∞ |
| f | ∞ | ∞ | 1 | ∞ | 5 | 0 | ∞ | ∞ |
| g | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 | 2 |
| h | ∞ | ∞ | ∞ | ∞ | 5 | 1 | ∞ | 0 |
D[0,7] = min{D[0,3]+D[3,7], D[0,7]}=min{2+4,∞}=6
=>Vì trong bảng trước, D[0,7]=∞ > 6
=>Nên Chúng ta cập nhật D[0,7]=6
Bảng sau khi cập nhật D[0,7]:
| D | a | b | c | d | e | f | g | h |
| a | 0 | 4 | ∞ | 2 | 6 | ∞ | 3 | 6 |
| b | ∞ | 0 | ∞ | ∞ | 2 | ∞ | ∞ | ∞ |
| c | ∞ | ∞ | 0 | ∞ | 4 | ∞ | ∞ | ∞ |
| d | ∞ | ∞ | ∞ | 0 | ∞ | ∞ | 1 | 4 |
| e | ∞ | ∞ | ∞ | ∞ | 0 | 2 | ∞ | ∞ |
| f | ∞ | ∞ | 1 | ∞ | 5 | 0 | ∞ | ∞ |
| g | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 | 2 |
| h | ∞ | ∞ | ∞ | ∞ | 5 | 1 | ∞ | 0 |
D[1,0] = min{D[1,3]+D[3,0], D[1,0]}=min{∞+∞,∞}=∞
D[1,2] = min{D[1,3]+D[3,2], D[1,2]}=min{∞+∞,∞}=∞
D[1,4] = min{D[1,3]+D[3,4], D[1,4]}=min{∞+∞,2}=2
D[1,5] = min{D[1,3]+D[3,5], D[1,5]}=min{∞+∞,∞}=∞
D[1,6] = min{D[1,3]+D[3,6], D[1,6]}=min{∞+1,∞}=∞
D[1,7] = min{D[1,3]+D[3,7], D[1,7]}=min{∞+4,∞}=∞
D[2,0] = min{D[2,3]+D[3,0], D[2,0]}=min{∞+∞,∞}=∞
D[2,1] = min{D[2,3]+D[3,1], D[2,1]}=min{∞+∞,∞}=∞
D[2,4] = min{D[2,3]+D[3,4], D[2,4]}=min{∞+∞,4}=4
D[2,5] = min{D[2,3]+D[3,5], D[2,5]}=min{∞+∞,∞}=∞
D[2,6] = min{D[2,3]+D[3,6], D[2,6]}=min{∞+1,∞}=∞
D[2,7] = min{D[2,3]+D[3,7], D[2,7]}=min{∞+4,∞}=∞
D[4,0] = min{D[4,3]+D[3,0], D[4,0]}=min{∞+∞,∞}=∞
D[4,1] = min{D[4,3]+D[3,1], D[4,1]}=min{∞+∞,∞}=∞
D[4,2] = min{D[4,3]+D[3,2], D[4,2]}=min{∞+∞,∞}=∞
D[4,5] = min{D[4,3]+D[3,5], D[4,5]}=min{∞+∞,2}=2
D[4,6] = min{D[4,3]+D[3,6], D[4,6]}=min{∞+1,∞}=∞
D[4,7] = min{D[4,3]+D[3,7], D[4,7]}=min{∞+4,∞}=∞
D[5,0] = min{D[5,3]+D[3,0], D[5,0]}=min{∞+∞,∞}=∞
D[5,1] = min{D[5,3]+D[3,1], D[5,1]}=min{∞+∞,∞}=∞
D[5,2] = min{D[5,3]+D[3,2], D[5,2]}=min{∞+∞,1}=1
D[5,4] = min{D[5,3]+D[3,4], D[5,4]}=min{∞+∞,5}=5
D[5,6] = min{D[5,3]+D[3,6], D[5,6]}=min{∞+1,∞}=∞
D[5,7] = min{D[5,3]+D[3,7], D[5,7]}=min{∞+4,∞}=∞
D[6,0] = min{D[6,3]+D[3,0], D[6,0]}=min{∞+∞,∞}=∞
D[6,1] = min{D[6,3]+D[3,1], D[6,1]}=min{∞+∞,∞}=∞
D[6,2] = min{D[6,3]+D[3,2], D[6,2]}=min{∞+∞,∞}=∞
D[6,4] = min{D[6,3]+D[3,4], D[6,4]}=min{∞+∞,∞}=∞
D[6,5] = min{D[6,3]+D[3,5], D[6,5]}=min{∞+∞,∞}=∞
D[6,7] = min{D[6,3]+D[3,7], D[6,7]}=min{∞+4,2}=2
D[7,0] = min{D[7,3]+D[3,0], D[7,0]}=min{∞+∞,∞}=∞
D[7,1] = min{D[7,3]+D[3,1], D[7,1]}=min{∞+∞,∞}=∞
D[7,2] = min{D[7,3]+D[3,2], D[7,2]}=min{∞+∞,∞}=∞
D[7,4] = min{D[7,3]+D[3,4], D[7,4]}=min{∞+∞,5}=5
D[7,5] = min{D[7,3]+D[3,5], D[7,5]}=min{∞+∞,1}=1
D[7,6] = min{D[7,3]+D[3,6], D[7,6]}=min{∞+1,∞}=∞
Khi K =4:
D[0,1] = min{D[0,4]+D[4,1], D[0,1]}=min{6+∞,4}=4
D[0,2] = min{D[0,4]+D[4,2], D[0,2]}=min{6+∞,∞}=∞
D[0,3] = min{D[0,4]+D[4,3], D[0,3]}=min{6+∞,2}=2
D[0,5] = min{D[0,4]+D[4,5], D[0,5]}=min{6+2,∞}=8
=>Vì trong bảng trước, D[0,5]=∞ > 8
=>Nên Chúng ta cập nhật D[0,5]=8
Bảng sau khi cập nhật D[0,5]:
| D | a | b | c | d | e | f | g | h |
| a | 0 | 4 | ∞ | 2 | 6 | 8 | 3 | 6 |
| b | ∞ | 0 | ∞ | ∞ | 2 | ∞ | ∞ | ∞ |
| c | ∞ | ∞ | 0 | ∞ | 4 | ∞ | ∞ | ∞ |
| d | ∞ | ∞ | ∞ | 0 | ∞ | ∞ | 1 | 4 |
| e | ∞ | ∞ | ∞ | ∞ | 0 | 2 | ∞ | ∞ |
| f | ∞ | ∞ | 1 | ∞ | 5 | 0 | ∞ | ∞ |
| g | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 | 2 |
| h | ∞ | ∞ | ∞ | ∞ | 5 | 1 | ∞ | 0 |
D[0,6] = min{D[0,4]+D[4,6], D[0,6]}=min{6+∞,3}=3
D[0,7] = min{D[0,4]+D[4,7], D[0,7]}=min{6+∞,6}=6
D[1,0] = min{D[1,4]+D[4,0], D[1,0]}=min{2+∞,∞}=∞
D[1,2] = min{D[1,4]+D[4,2], D[1,2]}=min{2+∞,∞}=∞
D[1,3] = min{D[1,4]+D[4,3], D[1,3]}=min{2+∞,∞}=∞
D[1,5] = min{D[1,4]+D[4,5], D[1,5]}=min{2+2,∞}=4
=>Vì trong bảng trước, D[1,5]=∞ > 4
=>Nên Chúng ta cập nhật D[1,5]=4
Bảng sau khi cập nhật D[1,5]:
| D | a | b | c | d | e | f | g | h |
| a | 0 | 4 | ∞ | 2 | 6 | 8 | 3 | 6 |
| b | ∞ | 0 | ∞ | ∞ | 2 | 4 | ∞ | ∞ |
| c | ∞ | ∞ | 0 | ∞ | 4 | ∞ | ∞ | ∞ |
| d | ∞ | ∞ | ∞ | 0 | ∞ | ∞ | 1 | 4 |
| e | ∞ | ∞ | ∞ | ∞ | 0 | 2 | ∞ | ∞ |
| f | ∞ | ∞ | 1 | ∞ | 5 | 0 | ∞ | ∞ |
| g | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 | 2 |
| h | ∞ | ∞ | ∞ | ∞ | 5 | 1 | ∞ | 0 |
D[1,6] = min{D[1,4]+D[4,6], D[1,6]}=min{2+∞,∞}=∞
D[1,7] = min{D[1,4]+D[4,7], D[1,7]}=min{2+∞,∞}=∞
D[2,0] = min{D[2,4]+D[4,0], D[2,0]}=min{4+∞,∞}=∞
D[2,1] = min{D[2,4]+D[4,1], D[2,1]}=min{4+∞,∞}=∞
D[2,3] = min{D[2,4]+D[4,3], D[2,3]}=min{4+∞,∞}=∞
D[2,5] = min{D[2,4]+D[4,5], D[2,5]}=min{4+2,∞}=6
=>Vì trong bảng trước, D[2,5]=∞ > 6
=>Nên Chúng ta cập nhật D[2,5]=6
Bảng sau khi cập nhật D[2,5]:
| D | a | b | c | d | e | f | g | h |
| a | 0 | 4 | ∞ | 2 | 6 | 8 | 3 | 6 |
| b | ∞ | 0 | ∞ | ∞ | 2 | 4 | ∞ | ∞ |
| c | ∞ | ∞ | 0 | ∞ | 4 | 6 | ∞ | ∞ |
| d | ∞ | ∞ | ∞ | 0 | ∞ | ∞ | 1 | 4 |
| e | ∞ | ∞ | ∞ | ∞ | 0 | 2 | ∞ | ∞ |
| f | ∞ | ∞ | 1 | ∞ | 5 | 0 | ∞ | ∞ |
| g | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 | 2 |
| h | ∞ | ∞ | ∞ | ∞ | 5 | 1 | ∞ | 0 |
D[2,6] = min{D[2,4]+D[4,6], D[2,6]}=min{4+∞,∞}=∞
D[2,7] = min{D[2,4]+D[4,7], D[2,7]}=min{4+∞,∞}=∞
D[3,0] = min{D[3,4]+D[4,0], D[3,0]}=min{∞+∞,∞}=∞
D[3,1] = min{D[3,4]+D[4,1], D[3,1]}=min{∞+∞,∞}=∞
D[3,2] = min{D[3,4]+D[4,2], D[3,2]}=min{∞+∞,∞}=∞
D[3,5] = min{D[3,4]+D[4,5], D[3,5]}=min{∞+2,∞}=∞
D[3,6] = min{D[3,4]+D[4,6], D[3,6]}=min{∞+∞,1}=1
D[3,7] = min{D[3,4]+D[4,7], D[3,7]}=min{∞+∞,4}=4
D[5,0] = min{D[5,4]+D[4,0], D[5,0]}=min{5+∞,∞}=∞
D[5,1] = min{D[5,4]+D[4,1], D[5,1]}=min{5+∞,∞}=∞
D[5,2] = min{D[5,4]+D[4,2], D[5,2]}=min{5+∞,1}=1
D[5,3] = min{D[5,4]+D[4,3], D[5,3]}=min{5+∞,∞}=∞
D[5,6] = min{D[5,4]+D[4,6], D[5,6]}=min{5+∞,∞}=∞
D[5,7] = min{D[5,4]+D[4,7], D[5,7]}=min{5+∞,∞}=∞
D[6,0] = min{D[6,4]+D[4,0], D[6,0]}=min{∞+∞,∞}=∞
D[6,1] = min{D[6,4]+D[4,1], D[6,1]}=min{∞+∞,∞}=∞
D[6,2] = min{D[6,4]+D[4,2], D[6,2]}=min{∞+∞,∞}=∞
D[6,3] = min{D[6,4]+D[4,3], D[6,3]}=min{∞+∞,∞}=∞
D[6,5] = min{D[6,4]+D[4,5], D[6,5]}=min{∞+2,∞}=∞
D[6,7] = min{D[6,4]+D[4,7], D[6,7]}=min{∞+∞,2}=2
D[7,0] = min{D[7,4]+D[4,0], D[7,0]}=min{5+∞,∞}=∞
D[7,1] = min{D[7,4]+D[4,1], D[7,1]}=min{5+∞,∞}=∞
D[7,2] = min{D[7,4]+D[4,2], D[7,2]}=min{5+∞,∞}=∞
D[7,3] = min{D[7,4]+D[4,3], D[7,3]}=min{5+∞,∞}=∞
D[7,5] = min{D[7,4]+D[4,5], D[7,5]}=min{5+2,1}=1
D[7,6] = min{D[7,4]+D[4,6], D[7,6]}=min{5+∞,∞}=∞
Khi K =5:
D[0,1] = min{D[0,5]+D[5,1], D[0,1]}=min{8+∞,4}=4
D[0,2] = min{D[0,5]+D[5,2], D[0,2]}=min{8+1,∞}=9
=>Vì trong bảng trước, D[0,2]=∞ > 9
=>Nên Chúng ta cập nhật D[0,2]=9
Bảng sau khi cập nhật D[0,2]:
| D | a | b | c | d | e | f | g | h |
| a | 0 | 4 | 9 | 2 | 6 | 8 | 3 | 6 |
| b | ∞ | 0 | ∞ | ∞ | 2 | 4 | ∞ | ∞ |
| c | ∞ | ∞ | 0 | ∞ | 4 | 6 | ∞ | ∞ |
| d | ∞ | ∞ | ∞ | 0 | ∞ | ∞ | 1 | 4 |
| e | ∞ | ∞ | ∞ | ∞ | 0 | 2 | ∞ | ∞ |
| f | ∞ | ∞ | 1 | ∞ | 5 | 0 | ∞ | ∞ |
| g | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 | 2 |
| h | ∞ | ∞ | ∞ | ∞ | 5 | 1 | ∞ | 0 |
D[0,3] = min{D[0,5]+D[5,3], D[0,3]}=min{8+∞,2}=2
D[0,4] = min{D[0,5]+D[5,4], D[0,4]}=min{8+5,6}=6
D[0,6] = min{D[0,5]+D[5,6], D[0,6]}=min{8+∞,3}=3
D[0,7] = min{D[0,5]+D[5,7], D[0,7]}=min{8+∞,6}=6
D[1,0] = min{D[1,5]+D[5,0], D[1,0]}=min{4+∞,∞}=∞
D[1,2] = min{D[1,5]+D[5,2], D[1,2]}=min{4+1,∞}=5
=>Vì trong bảng trước, D[1,2]=∞ > 5
=>Nên Chúng ta cập nhật D[1,2]=5
Bảng sau khi cập nhật D[1,2]:
| D | a | b | c | d | e | f | g | h |
| a | 0 | 4 | 9 | 2 | 6 | 8 | 3 | 6 |
| b | ∞ | 0 | 5 | ∞ | 2 | 4 | ∞ | ∞ |
| c | ∞ | ∞ | 0 | ∞ | 4 | 6 | ∞ | ∞ |
| d | ∞ | ∞ | ∞ | 0 | ∞ | ∞ | 1 | 4 |
| e | ∞ | ∞ | ∞ | ∞ | 0 | 2 | ∞ | ∞ |
| f | ∞ | ∞ | 1 | ∞ | 5 | 0 | ∞ | ∞ |
| g | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 | 2 |
| h | ∞ | ∞ | ∞ | ∞ | 5 | 1 | ∞ | 0 |
D[1,3] = min{D[1,5]+D[5,3], D[1,3]}=min{4+∞,∞}=∞
D[1,4] = min{D[1,5]+D[5,4], D[1,4]}=min{4+5,2}=2
D[1,6] = min{D[1,5]+D[5,6], D[1,6]}=min{4+∞,∞}=∞
D[1,7] = min{D[1,5]+D[5,7], D[1,7]}=min{4+∞,∞}=∞
D[2,0] = min{D[2,5]+D[5,0], D[2,0]}=min{6+∞,∞}=∞
D[2,1] = min{D[2,5]+D[5,1], D[2,1]}=min{6+∞,∞}=∞
D[2,3] = min{D[2,5]+D[5,3], D[2,3]}=min{6+∞,∞}=∞
D[2,4] = min{D[2,5]+D[5,4], D[2,4]}=min{6+5,4}=4
D[2,6] = min{D[2,5]+D[5,6], D[2,6]}=min{6+∞,∞}=∞
D[2,7] = min{D[2,5]+D[5,7], D[2,7]}=min{6+∞,∞}=∞
D[3,0] = min{D[3,5]+D[5,0], D[3,0]}=min{∞+∞,∞}=∞
D[3,1] = min{D[3,5]+D[5,1], D[3,1]}=min{∞+∞,∞}=∞
D[3,2] = min{D[3,5]+D[5,2], D[3,2]}=min{∞+1,∞}=∞
D[3,4] = min{D[3,5]+D[5,4], D[3,4]}=min{∞+5,∞}=∞
D[3,6] = min{D[3,5]+D[5,6], D[3,6]}=min{∞+∞,1}=1
D[3,7] = min{D[3,5]+D[5,7], D[3,7]}=min{∞+∞,4}=4
D[4,0] = min{D[4,5]+D[5,0], D[4,0]}=min{2+∞,∞}=∞
D[4,1] = min{D[4,5]+D[5,1], D[4,1]}=min{2+∞,∞}=∞
D[4,2] = min{D[4,5]+D[5,2], D[4,2]}=min{2+1,∞}=3
=>Vì trong bảng trước, D[4,2]=∞ > 3
=>Nên Chúng ta cập nhật D[4,2]=3
Bảng sau khi cập nhật D[4,2]:
| D | a | b | c | d | e | f | g | h |
| a | 0 | 4 | 9 | 2 | 6 | 8 | 3 | 6 |
| b | ∞ | 0 | 5 | ∞ | 2 | 4 | ∞ | ∞ |
| c | ∞ | ∞ | 0 | ∞ | 4 | 6 | ∞ | ∞ |
| d | ∞ | ∞ | ∞ | 0 | ∞ | ∞ | 1 | 4 |
| e | ∞ | ∞ | 3 | ∞ | 0 | 2 | ∞ | ∞ |
| f | ∞ | ∞ | 1 | ∞ | 5 | 0 | ∞ | ∞ |
| g | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 | 2 |
| h | ∞ | ∞ | ∞ | ∞ | 5 | 1 | ∞ | 0 |
D[4,3] = min{D[4,5]+D[5,3], D[4,3]}=min{2+∞,∞}=∞
D[4,6] = min{D[4,5]+D[5,6], D[4,6]}=min{2+∞,∞}=∞
D[4,7] = min{D[4,5]+D[5,7], D[4,7]}=min{2+∞,∞}=∞
D[6,0] = min{D[6,5]+D[5,0], D[6,0]}=min{∞+∞,∞}=∞
D[6,1] = min{D[6,5]+D[5,1], D[6,1]}=min{∞+∞,∞}=∞
D[6,2] = min{D[6,5]+D[5,2], D[6,2]}=min{∞+1,∞}=∞
D[6,3] = min{D[6,5]+D[5,3], D[6,3]}=min{∞+∞,∞}=∞
D[6,4] = min{D[6,5]+D[5,4], D[6,4]}=min{∞+5,∞}=∞
D[6,7] = min{D[6,5]+D[5,7], D[6,7]}=min{∞+∞,2}=2
D[7,0] = min{D[7,5]+D[5,0], D[7,0]}=min{1+∞,∞}=∞
D[7,1] = min{D[7,5]+D[5,1], D[7,1]}=min{1+∞,∞}=∞
D[7,2] = min{D[7,5]+D[5,2], D[7,2]}=min{1+1,∞}=2
=>Vì trong bảng trước, D[7,2]=∞ > 2
=>Nên Chúng ta cập nhật D[7,2]=2
Bảng sau khi cập nhật D[7,2]:
| D | a | b | c | d | e | f | g | h |
| a | 0 | 4 | 9 | 2 | 6 | 8 | 3 | 6 |
| b | ∞ | 0 | 5 | ∞ | 2 | 4 | ∞ | ∞ |
| c | ∞ | ∞ | 0 | ∞ | 4 | 6 | ∞ | ∞ |
| d | ∞ | ∞ | ∞ | 0 | ∞ | ∞ | 1 | 4 |
| e | ∞ | ∞ | 3 | ∞ | 0 | 2 | ∞ | ∞ |
| f | ∞ | ∞ | 1 | ∞ | 5 | 0 | ∞ | ∞ |
| g | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 | 2 |
| h | ∞ | ∞ | 2 | ∞ | 5 | 1 | ∞ | 0 |
D[7,3] = min{D[7,5]+D[5,3], D[7,3]}=min{1+∞,∞}=∞
D[7,4] = min{D[7,5]+D[5,4], D[7,4]}=min{1+5,5}=5
D[7,6] = min{D[7,5]+D[5,6], D[7,6]}=min{1+∞,∞}=∞
Khi K =6:
D[0,1] = min{D[0,6]+D[6,1], D[0,1]}=min{3+∞,4}=4
D[0,2] = min{D[0,6]+D[6,2], D[0,2]}=min{3+∞,9}=9
D[0,3] = min{D[0,6]+D[6,3], D[0,3]}=min{3+∞,2}=2
D[0,4] = min{D[0,6]+D[6,4], D[0,4]}=min{3+∞,6}=6
D[0,5] = min{D[0,6]+D[6,5], D[0,5]}=min{3+∞,8}=8
D[0,7] = min{D[0,6]+D[6,7], D[0,7]}=min{3+2,6}=5
=>Vì trong bảng trước, D[0,7]=6 > 5
=>Nên Chúng ta cập nhật D[0,7]=5
Bảng sau khi cập nhật D[0,7]:
| D | a | b | c | d | e | f | g | h |
| a | 0 | 4 | 9 | 2 | 6 | 8 | 3 | 5 |
| b | ∞ | 0 | 5 | ∞ | 2 | 4 | ∞ | ∞ |
| c | ∞ | ∞ | 0 | ∞ | 4 | 6 | ∞ | ∞ |
| d | ∞ | ∞ | ∞ | 0 | ∞ | ∞ | 1 | 4 |
| e | ∞ | ∞ | 3 | ∞ | 0 | 2 | ∞ | ∞ |
| f | ∞ | ∞ | 1 | ∞ | 5 | 0 | ∞ | ∞ |
| g | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 | 2 |
| h | ∞ | ∞ | 2 | ∞ | 5 | 1 | ∞ | 0 |
D[1,0] = min{D[1,6]+D[6,0], D[1,0]}=min{∞+∞,∞}=∞
D[1,2] = min{D[1,6]+D[6,2], D[1,2]}=min{∞+∞,5}=5
D[1,3] = min{D[1,6]+D[6,3], D[1,3]}=min{∞+∞,∞}=∞
D[1,4] = min{D[1,6]+D[6,4], D[1,4]}=min{∞+∞,2}=2
D[1,5] = min{D[1,6]+D[6,5], D[1,5]}=min{∞+∞,4}=4
D[1,7] = min{D[1,6]+D[6,7], D[1,7]}=min{∞+2,∞}=∞
D[2,0] = min{D[2,6]+D[6,0], D[2,0]}=min{∞+∞,∞}=∞
D[2,1] = min{D[2,6]+D[6,1], D[2,1]}=min{∞+∞,∞}=∞
D[2,3] = min{D[2,6]+D[6,3], D[2,3]}=min{∞+∞,∞}=∞
D[2,4] = min{D[2,6]+D[6,4], D[2,4]}=min{∞+∞,4}=4
D[2,5] = min{D[2,6]+D[6,5], D[2,5]}=min{∞+∞,6}=6
D[2,7] = min{D[2,6]+D[6,7], D[2,7]}=min{∞+2,∞}=∞
D[3,0] = min{D[3,6]+D[6,0], D[3,0]}=min{1+∞,∞}=∞
D[3,1] = min{D[3,6]+D[6,1], D[3,1]}=min{1+∞,∞}=∞
D[3,2] = min{D[3,6]+D[6,2], D[3,2]}=min{1+∞,∞}=∞
D[3,4] = min{D[3,6]+D[6,4], D[3,4]}=min{1+∞,∞}=∞
D[3,5] = min{D[3,6]+D[6,5], D[3,5]}=min{1+∞,∞}=∞
D[3,7] = min{D[3,6]+D[6,7], D[3,7]}=min{1+2,4}=3
=>Vì trong bảng trước, D[3,7]=4 > 3
=>Nên Chúng ta cập nhật D[3,7]=3
Bảng sau khi cập nhật D[3,7]:
| D | a | b | c | d | e | f | g | h |
| a | 0 | 4 | 9 | 2 | 6 | 8 | 3 | 5 |
| b | ∞ | 0 | 5 | ∞ | 2 | 4 | ∞ | ∞ |
| c | ∞ | ∞ | 0 | ∞ | 4 | 6 | ∞ | ∞ |
| d | ∞ | ∞ | ∞ | 0 | ∞ | ∞ | 1 | 3 |
| e | ∞ | ∞ | 3 | ∞ | 0 | 2 | ∞ | ∞ |
| f | ∞ | ∞ | 1 | ∞ | 5 | 0 | ∞ | ∞ |
| g | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 | 2 |
| h | ∞ | ∞ | 2 | ∞ | 5 | 1 | ∞ | 0 |
D[4,0] = min{D[4,6]+D[6,0], D[4,0]}=min{∞+∞,∞}=∞
D[4,1] = min{D[4,6]+D[6,1], D[4,1]}=min{∞+∞,∞}=∞
D[4,2] = min{D[4,6]+D[6,2], D[4,2]}=min{∞+∞,3}=3
D[4,3] = min{D[4,6]+D[6,3], D[4,3]}=min{∞+∞,∞}=∞
D[4,5] = min{D[4,6]+D[6,5], D[4,5]}=min{∞+∞,2}=2
D[4,7] = min{D[4,6]+D[6,7], D[4,7]}=min{∞+2,∞}=∞
D[5,0] = min{D[5,6]+D[6,0], D[5,0]}=min{∞+∞,∞}=∞
D[5,1] = min{D[5,6]+D[6,1], D[5,1]}=min{∞+∞,∞}=∞
D[5,2] = min{D[5,6]+D[6,2], D[5,2]}=min{∞+∞,1}=1
D[5,3] = min{D[5,6]+D[6,3], D[5,3]}=min{∞+∞,∞}=∞
D[5,4] = min{D[5,6]+D[6,4], D[5,4]}=min{∞+∞,5}=5
D[5,7] = min{D[5,6]+D[6,7], D[5,7]}=min{∞+2,∞}=∞
D[7,0] = min{D[7,6]+D[6,0], D[7,0]}=min{∞+∞,∞}=∞
D[7,1] = min{D[7,6]+D[6,1], D[7,1]}=min{∞+∞,∞}=∞
D[7,2] = min{D[7,6]+D[6,2], D[7,2]}=min{∞+∞,2}=2
D[7,3] = min{D[7,6]+D[6,3], D[7,3]}=min{∞+∞,∞}=∞
D[7,4] = min{D[7,6]+D[6,4], D[7,4]}=min{∞+∞,5}=5
D[7,5] = min{D[7,6]+D[6,5], D[7,5]}=min{∞+∞,1}=1
Khi K =7:
D[0,1] = min{D[0,7]+D[7,1], D[0,1]}=min{5+∞,4}=4
D[0,2] = min{D[0,7]+D[7,2], D[0,2]}=min{5+2,9}=7
=>Vì trong bảng trước, D[0,2]=9 > 7
=>Nên Chúng ta cập nhật D[0,2]=7
Bảng sau khi cập nhật D[0,2]:
| D | a | b | c | d | e | f | g | h |
| a | 0 | 4 | 7 | 2 | 6 | 8 | 3 | 5 |
| b | ∞ | 0 | 5 | ∞ | 2 | 4 | ∞ | ∞ |
| c | ∞ | ∞ | 0 | ∞ | 4 | 6 | ∞ | ∞ |
| d | ∞ | ∞ | ∞ | 0 | ∞ | ∞ | 1 | 3 |
| e | ∞ | ∞ | 3 | ∞ | 0 | 2 | ∞ | ∞ |
| f | ∞ | ∞ | 1 | ∞ | 5 | 0 | ∞ | ∞ |
| g | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 | 2 |
| h | ∞ | ∞ | 2 | ∞ | 5 | 1 | ∞ | 0 |
D[0,3] = min{D[0,7]+D[7,3], D[0,3]}=min{5+∞,2}=2
D[0,4] = min{D[0,7]+D[7,4], D[0,4]}=min{5+5,6}=6
D[0,5] = min{D[0,7]+D[7,5], D[0,5]}=min{5+1,8}=6
=>Vì trong bảng trước, D[0,5]=8 > 6
=>Nên Chúng ta cập nhật D[0,5]=6
Bảng sau khi cập nhật D[0,5]:
| D | a | b | c | d | e | f | g | h |
| a | 0 | 4 | 7 | 2 | 6 | 6 | 3 | 5 |
| b | ∞ | 0 | 5 | ∞ | 2 | 4 | ∞ | ∞ |
| c | ∞ | ∞ | 0 | ∞ | 4 | 6 | ∞ | ∞ |
| d | ∞ | ∞ | ∞ | 0 | ∞ | ∞ | 1 | 3 |
| e | ∞ | ∞ | 3 | ∞ | 0 | 2 | ∞ | ∞ |
| f | ∞ | ∞ | 1 | ∞ | 5 | 0 | ∞ | ∞ |
| g | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 | 2 |
| h | ∞ | ∞ | 2 | ∞ | 5 | 1 | ∞ | 0 |
D[0,6] = min{D[0,7]+D[7,6], D[0,6]}=min{5+∞,3}=3
D[1,0] = min{D[1,7]+D[7,0], D[1,0]}=min{∞+∞,∞}=∞
D[1,2] = min{D[1,7]+D[7,2], D[1,2]}=min{∞+2,5}=5
D[1,3] = min{D[1,7]+D[7,3], D[1,3]}=min{∞+∞,∞}=∞
D[1,4] = min{D[1,7]+D[7,4], D[1,4]}=min{∞+5,2}=2
D[1,5] = min{D[1,7]+D[7,5], D[1,5]}=min{∞+1,4}=4
D[1,6] = min{D[1,7]+D[7,6], D[1,6]}=min{∞+∞,∞}=∞
D[2,0] = min{D[2,7]+D[7,0], D[2,0]}=min{∞+∞,∞}=∞
D[2,1] = min{D[2,7]+D[7,1], D[2,1]}=min{∞+∞,∞}=∞
D[2,3] = min{D[2,7]+D[7,3], D[2,3]}=min{∞+∞,∞}=∞
D[2,4] = min{D[2,7]+D[7,4], D[2,4]}=min{∞+5,4}=4
D[2,5] = min{D[2,7]+D[7,5], D[2,5]}=min{∞+1,6}=6
D[2,6] = min{D[2,7]+D[7,6], D[2,6]}=min{∞+∞,∞}=∞
D[3,0] = min{D[3,7]+D[7,0], D[3,0]}=min{3+∞,∞}=∞
D[3,1] = min{D[3,7]+D[7,1], D[3,1]}=min{3+∞,∞}=∞
D[3,2] = min{D[3,7]+D[7,2], D[3,2]}=min{3+2,∞}=5
=>Vì trong bảng trước, D[3,2]=∞ > 5
=>Nên Chúng ta cập nhật D[3,2]=5
Bảng sau khi cập nhật D[3,2]:
| D | a | b | c | d | e | f | g | h |
| a | 0 | 4 | 7 | 2 | 6 | 6 | 3 | 5 |
| b | ∞ | 0 | 5 | ∞ | 2 | 4 | ∞ | ∞ |
| c | ∞ | ∞ | 0 | ∞ | 4 | 6 | ∞ | ∞ |
| d | ∞ | ∞ | 5 | 0 | ∞ | ∞ | 1 | 3 |
| e | ∞ | ∞ | 3 | ∞ | 0 | 2 | ∞ | ∞ |
| f | ∞ | ∞ | 1 | ∞ | 5 | 0 | ∞ | ∞ |
| g | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 | 2 |
| h | ∞ | ∞ | 2 | ∞ | 5 | 1 | ∞ | 0 |
D[3,4] = min{D[3,7]+D[7,4], D[3,4]}=min{3+5,∞}=8
=>Vì trong bảng trước, D[3,4]=∞ > 8
=>Nên Chúng ta cập nhật D[3,4]=8
Bảng sau khi cập nhật D[3,4]:
| D | a | b | c | d | e | f | g | h |
| a | 0 | 4 | 7 | 2 | 6 | 6 | 3 | 5 |
| b | ∞ | 0 | 5 | ∞ | 2 | 4 | ∞ | ∞ |
| c | ∞ | ∞ | 0 | ∞ | 4 | 6 | ∞ | ∞ |
| d | ∞ | ∞ | 5 | 0 | 8 | ∞ | 1 | 3 |
| e | ∞ | ∞ | 3 | ∞ | 0 | 2 | ∞ | ∞ |
| f | ∞ | ∞ | 1 | ∞ | 5 | 0 | ∞ | ∞ |
| g | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 | 2 |
| h | ∞ | ∞ | 2 | ∞ | 5 | 1 | ∞ | 0 |
D[3,5] = min{D[3,7]+D[7,5], D[3,5]}=min{3+1,∞}=4
=>Vì trong bảng trước, D[3,5]=∞ > 4
=>Nên Chúng ta cập nhật D[3,5]=4
Bảng sau khi cập nhật D[3,5]:
| D | a | b | c | d | e | f | g | h |
| a | 0 | 4 | 7 | 2 | 6 | 6 | 3 | 5 |
| b | ∞ | 0 | 5 | ∞ | 2 | 4 | ∞ | ∞ |
| c | ∞ | ∞ | 0 | ∞ | 4 | 6 | ∞ | ∞ |
| d | ∞ | ∞ | 5 | 0 | 8 | 4 | 1 | 3 |
| e | ∞ | ∞ | 3 | ∞ | 0 | 2 | ∞ | ∞ |
| f | ∞ | ∞ | 1 | ∞ | 5 | 0 | ∞ | ∞ |
| g | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 | 2 |
| h | ∞ | ∞ | 2 | ∞ | 5 | 1 | ∞ | 0 |
D[3,6] = min{D[3,7]+D[7,6], D[3,6]}=min{3+∞,1}=1
D[4,0] = min{D[4,7]+D[7,0], D[4,0]}=min{∞+∞,∞}=∞
D[4,1] = min{D[4,7]+D[7,1], D[4,1]}=min{∞+∞,∞}=∞
D[4,2] = min{D[4,7]+D[7,2], D[4,2]}=min{∞+2,3}=3
D[4,3] = min{D[4,7]+D[7,3], D[4,3]}=min{∞+∞,∞}=∞
D[4,5] = min{D[4,7]+D[7,5], D[4,5]}=min{∞+1,2}=2
D[4,6] = min{D[4,7]+D[7,6], D[4,6]}=min{∞+∞,∞}=∞
D[5,0] = min{D[5,7]+D[7,0], D[5,0]}=min{∞+∞,∞}=∞
D[5,1] = min{D[5,7]+D[7,1], D[5,1]}=min{∞+∞,∞}=∞
D[5,2] = min{D[5,7]+D[7,2], D[5,2]}=min{∞+2,1}=1
D[5,3] = min{D[5,7]+D[7,3], D[5,3]}=min{∞+∞,∞}=∞
D[5,4] = min{D[5,7]+D[7,4], D[5,4]}=min{∞+5,5}=5
D[5,6] = min{D[5,7]+D[7,6], D[5,6]}=min{∞+∞,∞}=∞
D[6,0] = min{D[6,7]+D[7,0], D[6,0]}=min{2+∞,∞}=∞
D[6,1] = min{D[6,7]+D[7,1], D[6,1]}=min{2+∞,∞}=∞
D[6,2] = min{D[6,7]+D[7,2], D[6,2]}=min{2+2,∞}=4
=>Vì trong bảng trước, D[6,2]=∞ > 4
=>Nên Chúng ta cập nhật D[6,2]=4
Bảng sau khi cập nhật D[6,2]:
| D | a | b | c | d | e | f | g | h |
| a | 0 | 4 | 7 | 2 | 6 | 6 | 3 | 5 |
| b | ∞ | 0 | 5 | ∞ | 2 | 4 | ∞ | ∞ |
| c | ∞ | ∞ | 0 | ∞ | 4 | 6 | ∞ | ∞ |
| d | ∞ | ∞ | 5 | 0 | 8 | 4 | 1 | 3 |
| e | ∞ | ∞ | 3 | ∞ | 0 | 2 | ∞ | ∞ |
| f | ∞ | ∞ | 1 | ∞ | 5 | 0 | ∞ | ∞ |
| g | ∞ | ∞ | 4 | ∞ | ∞ | ∞ | 0 | 2 |
| h | ∞ | ∞ | 2 | ∞ | 5 | 1 | ∞ | 0 |
D[6,3] = min{D[6,7]+D[7,3], D[6,3]}=min{2+∞,∞}=∞
D[6,4] = min{D[6,7]+D[7,4], D[6,4]}=min{2+5,∞}=7
=>Vì trong bảng trước, D[6,4]=∞ > 7
=>Nên Chúng ta cập nhật D[6,4]=7
Bảng sau khi cập nhật D[6,4]:
| D | a | b | c | d | e | f | g | h |
| a | 0 | 4 | 7 | 2 | 6 | 6 | 3 | 5 |
| b | ∞ | 0 | 5 | ∞ | 2 | 4 | ∞ | ∞ |
| c | ∞ | ∞ | 0 | ∞ | 4 | 6 | ∞ | ∞ |
| d | ∞ | ∞ | 5 | 0 | 8 | 4 | 1 | 3 |
| e | ∞ | ∞ | 3 | ∞ | 0 | 2 | ∞ | ∞ |
| f | ∞ | ∞ | 1 | ∞ | 5 | 0 | ∞ | ∞ |
| g | ∞ | ∞ | 4 | ∞ | 7 | ∞ | 0 | 2 |
| h | ∞ | ∞ | 2 | ∞ | 5 | 1 | ∞ | 0 |
D[6,5] = min{D[6,7]+D[7,5], D[6,5]}=min{2+1,∞}=3
=>Vì trong bảng trước, D[6,5]=∞ > 3
=>Nên Chúng ta cập nhật D[6,5]=3
Bảng sau khi cập nhật D[6,5]:
| D | a | b | c | d | e | f | g | h |
| a | 0 | 4 | 7 | 2 | 6 | 6 | 3 | 5 |
| b | ∞ | 0 | 5 | ∞ | 2 | 4 | ∞ | ∞ |
| c | ∞ | ∞ | 0 | ∞ | 4 | 6 | ∞ | ∞ |
| d | ∞ | ∞ | 5 | 0 | 8 | 4 | 1 | 3 |
| e | ∞ | ∞ | 3 | ∞ | 0 | 2 | ∞ | ∞ |
| f | ∞ | ∞ | 1 | ∞ | 5 | 0 | ∞ | ∞ |
| g | ∞ | ∞ | 4 | ∞ | 7 | 3 | 0 | 2 |
| h | ∞ | ∞ | 2 | ∞ | 5 | 1 | ∞ | 0 |
Cuối cùng chúng ta có bảng kết quả lưu đường đi ngắn nhất qua mọi cặp đỉnh:
| D | a | b | c | d | e | f | g | h |
| a | 0 | 4 | 7 | 2 | 6 | 6 | 3 | 5 |
| b | ∞ | 0 | 5 | ∞ | 2 | 4 | ∞ | ∞ |
| c | ∞ | ∞ | 0 | ∞ | 4 | 6 | ∞ | ∞ |
| d | ∞ | ∞ | 5 | 0 | 8 | 4 | 1 | 3 |
| e | ∞ | ∞ | 3 | ∞ | 0 | 2 | ∞ | ∞ |
| f | ∞ | ∞ | 1 | ∞ | 5 | 0 | ∞ | ∞ |
| g | ∞ | ∞ | 4 | ∞ | 7 | 3 | 0 | 2 |
| h | ∞ | ∞ | 2 | ∞ | 5 | 1 | ∞ | 0 |
Minh họa phần mềm:
Video hướng dẫn sử dụng phần mền (phải xem để biết cách nhập 1 Đồ thị vào ma trận khởi tạo):
Phần mềm exe bấm vào chạy luôn :
https://www.mediafire.com/file/o952gboozvtv9ao/AllPairsShortest.exe/file
Source code chương trình:
https://www.mediafire.com/file/f1ykhgmcv2qowed/AllPairsShortest.rar/file
Nếu cảm thấy hữu ích thì hãy Ủng hộ Tui 1 ly cafe sữa đá lề đường
STK: 0101146302
Chủ TK: Trần Duy Thanh
Ngân Hàng: Đông Á, chi nhánh Gò Vấp
