đườ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∞
2∞01∞4
313012
4-2∞∞02
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∞
2∞01∞4
313012
4-22∞02
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∞
2∞01∞4
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
2∞01∞4
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
2∞01∞4
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
2∞01∞4
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
2∞01∞4
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
2201∞4
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
a04∞27∞∞∞
b∞0∞∞2∞∞∞
c∞∞0∞4∞∞∞
d∞∞∞0∞∞14
e∞∞∞∞02∞∞
f∞∞1∞∞0∞∞
g∞∞∞∞∞∞02
h∞∞∞∞51∞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]:

Dabcdefgh
a04∞26∞∞∞
b∞0∞∞2∞∞∞
c∞∞0∞4∞∞∞
d∞∞∞0∞∞14
e∞∞∞∞02∞∞
f∞∞1∞∞0∞∞
g∞∞∞∞∞∞02
h∞∞∞∞51∞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]:

Dabcdefgh
a04∞26∞∞∞
b∞0∞∞2∞∞∞
c∞∞0∞4∞∞∞
d∞∞∞0∞∞14
e∞∞∞∞02∞∞
f∞∞1∞50∞∞
g∞∞∞∞∞∞02
h∞∞∞∞51∞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]:

Dabcdefgh
a04∞26∞3∞
b∞0∞∞2∞∞∞
c∞∞0∞4∞∞∞
d∞∞∞0∞∞14
e∞∞∞∞02∞∞
f∞∞1∞50∞∞
g∞∞∞∞∞∞02
h∞∞∞∞51∞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]:

Dabcdefgh
a04∞26∞36
b∞0∞∞2∞∞∞
c∞∞0∞4∞∞∞
d∞∞∞0∞∞14
e∞∞∞∞02∞∞
f∞∞1∞50∞∞
g∞∞∞∞∞∞02
h∞∞∞∞51∞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]:

Dabcdefgh
a04∞26836
b∞0∞∞2∞∞∞
c∞∞0∞4∞∞∞
d∞∞∞0∞∞14
e∞∞∞∞02∞∞
f∞∞1∞50∞∞
g∞∞∞∞∞∞02
h∞∞∞∞51∞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]:

Dabcdefgh
a04∞26836
b∞0∞∞24∞∞
c∞∞0∞4∞∞∞
d∞∞∞0∞∞14
e∞∞∞∞02∞∞
f∞∞1∞50∞∞
g∞∞∞∞∞∞02
h∞∞∞∞51∞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]:

Dabcdefgh
a04∞26836
b∞0∞∞24∞∞
c∞∞0∞46∞∞
d∞∞∞0∞∞14
e∞∞∞∞02∞∞
f∞∞1∞50∞∞
g∞∞∞∞∞∞02
h∞∞∞∞51∞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]:

Dabcdefgh
a04926836
b∞0∞∞24∞∞
c∞∞0∞46∞∞
d∞∞∞0∞∞14
e∞∞∞∞02∞∞
f∞∞1∞50∞∞
g∞∞∞∞∞∞02
h∞∞∞∞51∞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]:

Dabcdefgh
a04926836
b∞05∞24∞∞
c∞∞0∞46∞∞
d∞∞∞0∞∞14
e∞∞∞∞02∞∞
f∞∞1∞50∞∞
g∞∞∞∞∞∞02
h∞∞∞∞51∞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]:

Dabcdefgh
a04926836
b∞05∞24∞∞
c∞∞0∞46∞∞
d∞∞∞0∞∞14
e∞∞3∞02∞∞
f∞∞1∞50∞∞
g∞∞∞∞∞∞02
h∞∞∞∞51∞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]:

Dabcdefgh
a04926836
b∞05∞24∞∞
c∞∞0∞46∞∞
d∞∞∞0∞∞14
e∞∞3∞02∞∞
f∞∞1∞50∞∞
g∞∞∞∞∞∞02
h∞∞2∞51∞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]:

Dabcdefgh
a04926835
b∞05∞24∞∞
c∞∞0∞46∞∞
d∞∞∞0∞∞14
e∞∞3∞02∞∞
f∞∞1∞50∞∞
g∞∞∞∞∞∞02
h∞∞2∞51∞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]:

Dabcdefgh
a04926835
b∞05∞24∞∞
c∞∞0∞46∞∞
d∞∞∞0∞∞13
e∞∞3∞02∞∞
f∞∞1∞50∞∞
g∞∞∞∞∞∞02
h∞∞2∞51∞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]:

Dabcdefgh
a04726835
b∞05∞24∞∞
c∞∞0∞46∞∞
d∞∞∞0∞∞13
e∞∞3∞02∞∞
f∞∞1∞50∞∞
g∞∞∞∞∞∞02
h∞∞2∞51∞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]:

Dabcdefgh
a04726635
b∞05∞24∞∞
c∞∞0∞46∞∞
d∞∞∞0∞∞13
e∞∞3∞02∞∞
f∞∞1∞50∞∞
g∞∞∞∞∞∞02
h∞∞2∞51∞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]:

Dabcdefgh
a04726635
b∞05∞24∞∞
c∞∞0∞46∞∞
d∞∞50∞∞13
e∞∞3∞02∞∞
f∞∞1∞50∞∞
g∞∞∞∞∞∞02
h∞∞2∞51∞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]:

Dabcdefgh
a04726635
b∞05∞24∞∞
c∞∞0∞46∞∞
d∞∞508∞13
e∞∞3∞02∞∞
f∞∞1∞50∞∞
g∞∞∞∞∞∞02
h∞∞2∞51∞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]:

Dabcdefgh
a04726635
b∞05∞24∞∞
c∞∞0∞46∞∞
d∞∞508413
e∞∞3∞02∞∞
f∞∞1∞50∞∞
g∞∞∞∞∞∞02
h∞∞2∞51∞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]:

Dabcdefgh
a04726635
b∞05∞24∞∞
c∞∞0∞46∞∞
d∞∞508413
e∞∞3∞02∞∞
f∞∞1∞50∞∞
g∞∞4∞∞∞02
h∞∞2∞51∞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]:

Dabcdefgh
a04726635
b∞05∞24∞∞
c∞∞0∞46∞∞
d∞∞508413
e∞∞3∞02∞∞
f∞∞1∞50∞∞
g∞∞4∞7∞02
h∞∞2∞51∞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]:

Dabcdefgh
a04726635
b∞05∞24∞∞
c∞∞0∞46∞∞
d∞∞508413
e∞∞3∞02∞∞
f∞∞1∞50∞∞
g∞∞4∞7302
h∞∞2∞51∞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:

Dabcdefgh
a04726635
b∞05∞24∞∞
c∞∞0∞46∞∞
d∞∞508413
e∞∞3∞02∞∞
f∞∞1∞50∞∞
g∞∞4∞7302
h∞∞2∞51∞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

facebookShare on Facebook
TwitterTweet
FollowFollow us
PinterestSave

Leave a Reply