đường đi ngắn nhất mọi cặp đỉnh (All pairs shortest path)

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:

D12345
10425
2014
313012
4-202
5-3310

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]:

D12345
10425
2014
313012
4-2202
5-3310

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]:

D12345
10425
2014
313012
4-22002
5-3310

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]:

D12345
104258
2014
313012
4-22002
5-3310

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]:

D12345
104258
2014
313012
4-22002
5-3-210

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]:

D12345
104238
2014
313012
4-22002
5-3-210

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]:

D12345
104234
2014
313012
4-22002
5-3-210

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]:

D12345
104234
22014
313012
4-22002
5-3-210

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]:

D12345
104234
220124
313012
4-22002
5-3-210

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]:

D12345
104234
220123
313012
4-22002
5-3-210

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]:

D12345
104234
220123
313012
4-22002
5-1-3-210

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]:

D12345
104234
220123
313012
4-22002
5-1-3-2-10

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]:

D12345
104234
200123
313012
4-22002
5-1-3-2-10

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]:

D12345
104234
200123
3-13012
4-22002
5-1-3-2-10

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]:

D12345
104234
200123
3-13012
4-22002
5-3-3-2-10

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]:

D12345
101234
200123
3-13012
4-22002
5-3-3-2-10

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]:

D12345
101234
200123
3-1-1012
4-22002
5-3-3-2-10

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]:

D12345
101234
200123
3-1-1012
4-2-1002
5-3-3-2-10

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:

D12345
101234
200123
3-1-1012
4-2-1002
5-3-3-2-10

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:

Dabcdefgh
a0427
b02
c04
d014
e02
f10
g02
h510

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]:

Dabcdefgh
a0426
b02
c04
d014
e02
f10
g02
h510

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]:

Dabcdefgh
a0426
b02
c04
d014
e02
f150
g02
h510

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]:

Dabcdefgh
a04263
b02
c04
d014
e02
f150
g02
h510

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]:

Dabcdefgh
a042636
b02
c04
d014
e02
f150
g02
h510

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]:

Dabcdefgh
a0426836
b02
c04
d014
e02
f150
g02
h510

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]:

Dabcdefgh
a0426836
b024
c04
d014
e02
f150
g02
h510

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]:

Dabcdefgh
a0426836
b024
c046
d014
e02
f150
g02
h510

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]:

Dabcdefgh
a04926836
b024
c046
d014
e02
f150
g02
h510

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]:

Dabcdefgh
a04926836
b0524
c046
d014
e02
f150
g02
h510

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]:

Dabcdefgh
a04926836
b0524
c046
d014
e302
f150
g02
h510

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]:

Dabcdefgh
a04926836
b0524
c046
d014
e302
f150
g02
h2510

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]:

Dabcdefgh
a04926835
b0524
c046
d014
e302
f150
g02
h2510

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]:

Dabcdefgh
a04926835
b0524
c046
d013
e302
f150
g02
h2510

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]:

Dabcdefgh
a04726835
b0524
c046
d013
e302
f150
g02
h2510

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]:

Dabcdefgh
a04726635
b0524
c046
d013
e302
f150
g02
h2510

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]:

Dabcdefgh
a04726635
b0524
c046
d5013
e302
f150
g02
h2510

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]:

Dabcdefgh
a04726635
b0524
c046
d50813
e302
f150
g02
h2510

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]:

Dabcdefgh
a04726635
b0524
c046
d508413
e302
f150
g02
h2510

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]:

Dabcdefgh
a04726635
b0524
c046
d508413
e302
f150
g402
h2510

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]:

Dabcdefgh
a04726635
b0524
c046
d508413
e302
f150
g4702
h2510

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]:

Dabcdefgh
a04726635
b0524
c046
d508413
e302
f150
g47302
h2510

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:

Dabcdefgh
a04726635
b0524
c046
d508413
e302
f150
g47302
h2510

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

Leave a Reply