Thuật toán Floyd-Warshall cho đồ thị dầy

<p style="text-align: justify;">Trong b&agrave;i viết n&agrave;y, ta sẽ c&ugrave;ng t&igrave;m hiểu về c&aacute;ch hoạt động của thuật to&aacute;n Floyd-Warshall được ứng dụng cho đồ thị đầy bằng v&iacute; dụ minh họa.</p> <h2 id="ftoc-heading-1" class="ftwp-heading" style="text-align: justify;">1. Kh&aacute;i niệm</h2> <p style="text-align: justify;">Thuật to&aacute;n Floyd-Warshall l&agrave; một thuật to&aacute;n t&igrave;m đường đi ngắn nhất giữa tất cả c&aacute;c cặp đỉnh trong một đồ thị c&oacute; trọng số. Thuật to&aacute;n n&agrave;y hoạt động cho cả đồ thị c&oacute; trọng số c&oacute; hướng v&agrave; v&ocirc; hướng. Tuy nhi&ecirc;n, n&oacute; kh&ocirc;ng hoạt động đối với c&aacute;c đồ thị c&oacute; chu kỳ trọng số &acirc;m (trong đ&oacute; tổng c&aacute;c cạnh trong một chu kỳ l&agrave; &acirc;m).</p> <p style="text-align: justify;"><strong>Ch&uacute; &yacute;: Đồ thị c&oacute; trọng số l&agrave; đồ thị trong đ&oacute; mỗi cạnh c&oacute; một gi&aacute; trị số được li&ecirc;n kết với n&oacute;.</strong></p> <p style="text-align: justify;">Thuật to&aacute;n Floyd-Warhshall c&ograve;n được gọi l&agrave; thuật to&aacute;n Floyd, thuật to&aacute;n Roy-Floyd, thuật to&aacute;n Roy-Warshall, hoặc thuật to&aacute;n WFI. Thuật to&aacute;n n&agrave;y tu&acirc;n theo c&aacute;ch tiếp cận quy hoạch động để t&igrave;m c&aacute;c đường đi ngắn nhất.</p> <h2 id="ftoc-heading-2" class="ftwp-heading" style="text-align: justify;">2. C&aacute;ch thức hoạt động của thuật to&aacute;n</h2> <ul> <li style="text-align: justify;">Giả sử ta c&oacute; đồ thị c&oacute; dạng như sau:</li> </ul> <p><img style="width: 100%;" src="../../../public_files/4b56e041-49ad-40a6-b58b-873077d4f56b" alt="thuat-toan-floyd-warshall" /></p> <p>Ta sẽ l&agrave;m theo c&aacute;c bước dưới đ&acirc;y để t&igrave;m đường đi ngắn nhất giữa tất cả c&aacute;c cặp đỉnh.</p> <ul> <li>Bước 1: Tạo một ma trận $A^0$ c&oacute; số chiều l&agrave; $n \times n$, trong đ&oacute; n l&agrave; số đỉnh. H&agrave;ng v&agrave; cột được lập chỉ số lần lượt l&agrave; i v&agrave; j. i v&agrave; j l&agrave; c&aacute;c đỉnh của đồ thị. <ul> <li>Mỗi &ocirc; $A[i][j]$ được lấp đầy bởi khoảng c&aacute;ch từ đỉnh thứ i tới đỉnh thứ j. Nếu kh&ocirc;ng c&oacute; đường đi n&agrave;o từ đỉnh I tới đỉnh j, th&igrave; &ocirc; sẽ được để gi&aacute; trị l&agrave; v&ocirc; cực.</li> </ul> </li> </ul> <p class="ql-center-displayed-equation" style="text-align: center;">$A^0 = \begin{bmatrix} 0 &amp; 3 &amp; \infty &amp; 5 \\ 2 &amp; 0 &amp; \infty &amp; 4 \\ \infty &amp; 1 &amp; 0 &amp; \infty \\ \infty &amp; \infty &amp; 2 &amp; 0\end{bmatrix}$</p> <ul> <li>Bước 2: B&acirc;y giờ, ta sẽ tạo ra một ma trận $A^1$ bằng c&aacute;ch sử dụng ma trận $A^0$.C&aacute;c phần tử trong cột đầu ti&ecirc;n v&agrave; h&agrave;ng đầu ti&ecirc;n được giữ nguy&ecirc;n. C&aacute;c &ocirc; c&ograve;n lại được điền theo c&aacute;ch sau. <ul> <li>Gọi k l&agrave; đỉnh trung gian tr&ecirc;n đường đi ngắn nhất từ điểm bắt đầu đến điểm đ&iacute;ch. Trong bước n&agrave;y, k l&agrave; đỉnh đầu ti&ecirc;n. A[i][j] được lấp đầy bởi</li> <li>$(A[i][k] + A[k][j])$ nếu $(A[i][k] + A[k][j])$&nbsp;</li> <li>Nếu khoảng c&aacute;ch trực tiếp từ điểm bắt đầu đến điểm đ&iacute;ch lớn hơn đường đi qua đỉnh k, th&igrave; &ocirc; được điền với gi&aacute; trị l&agrave; $A[i][k] + A[k][j]$.</li> <li>Trong bước n&agrave;y, k l&agrave; đỉnh 1. Ta sẽ t&iacute;nh khoảng c&aacute;ch từ đỉnh nguồn đến đỉnh đ&iacute;ch th&ocirc;ng qua đỉnh $k$ n&agrave;y.</li> </ul> </li> </ul> <p style="text-align: center;">$A^1 = \begin{bmatrix} 0 &amp; 3 &amp; \infty &amp; 5 \\ 2 &amp; 0 &amp; \ &amp; \ \\ \infty &amp; \ &amp; 0 &amp; \ \\ \infty &amp; \ &amp;&nbsp; \ &amp; 0 \end{bmatrix} \rightarrow \begin{bmatrix} 0 &amp; 3 &amp; \infty &amp; 5\\2&amp; 0 &amp; 4 &amp; 9 \\ \infty &amp; 1 &amp; 0 &amp; 8 \\\infty &amp; \infty &amp; 2 &amp; 0 \end{bmatrix}$</p> <ul> <li style="list-style-type: none;"> <ul> <li>V&iacute; dụ:&nbsp; Với $A^1[2, 4]$, th&igrave; khoảng c&aacute;ch trực tiếp từ đỉnh 2 đến 4 l&agrave; 4 v&agrave; tổng khoảng c&aacute;ch từ đỉnh 2 đến 4 qua đỉnh (từ đỉnh 2 đến 1 v&agrave; từ đỉnh 1 đến 4) l&agrave; 7. V&igrave; 4 &lt; 7, $A^0[2, 4]$&nbsp;được điền gi&aacute; trị l&agrave; 4.</li> </ul> </li> </ul> <ul> <li>Bước 3: Tương tự, $A^2$ được tạo bằng c&aacute;ch sử dụng $A^1$. C&aacute;c phần tử trong cột thứ hai v&agrave; h&agrave;ng thứ hai được giữ nguy&ecirc;n. <ul> <li>Trong bước n&agrave;y, k l&agrave; đỉnh thứ hai (tức l&agrave; đỉnh 2). C&aacute;c bước c&ograve;n lại tương tự như bước 2.</li> </ul> </li> </ul> <p style="text-align: center;">$A^2 = \begin{bmatrix} 0 &amp; 3 &amp; \ &amp; \ \\ 2 &amp; 0 &amp; 9 &amp; 4 \\ \ &amp; 1 &amp; 0 &amp; \ \\ \ &amp; \infty &amp; \ &amp; 0 \end{bmatrix} \rightarrow \begin{bmatrix} 0 &amp; 3 &amp; 9 &amp; 5 \\ 2 &amp; 0 &amp; 9 &amp; 4 \\ 3 &amp; 1 &amp; 0 &amp; 5\\ \infty &amp; \infty &amp; 2 &amp; 0 \end{bmatrix}$</p> <ul> <li>Bước 4: Tương tự, $A^3$ v&agrave; $A^4$ cũng được tạo.</li> </ul> <p style="text-align: center;">$A^3 = \begin{bmatrix} 0 &amp; \ &amp; \infty &amp; \ \\ \ &amp; 0 &amp; 9 &amp; \ \\ \infty &amp; 1 &amp; 0 &amp; 8 \\ \ &amp; \ &amp; 2 &amp; 0 \end{bmatrix} \rightarrow \begin{bmatrix} 0 &amp; 3 &amp; 9 &amp; 5 \\ 2 &amp; 0 &amp; 9 &amp; 4 \\ 3 &amp; 1 &amp; 0 &amp; 5\\ 5 &amp; 3 &amp; 2 &amp; 0 \end{bmatrix}$</p> <p style="text-align: center;">$A^4 = \begin{bmatrix} 0 &amp; \ &amp; \ &amp; 5 \\ \ &amp; 0 &amp; \ &amp; 4 \\ \ &amp; \ &amp; 0 &amp; 5 \\ 5 &amp; 3 &amp; 2 &amp; 0 \end{bmatrix} \rightarrow \begin{bmatrix} 0 &amp; 3 &amp; 7 &amp; 5 \\ 2 &amp; 0 &amp; 6 &amp; 4 \\ 3 &amp; 1 &amp; 0 &amp; 5\\ 5 &amp; 3 &amp; 2 &amp; 0 \end{bmatrix}$</p> <ul> <li>$A^4$ đưa ra đường đi ngắn nhất giữa mỗi cặp đỉnh.</li> </ul> <p>Thuật to&aacute;n Floyd-Warshall được triển khai như sau:</p> <ul> <li>$n$ l&agrave; số lượng c&aacute;c đỉnh</li> <li>$A$ l&agrave; ma trận với số chiều l&agrave; $n \times n$</li> <li>V&ograve;ng lặp for với k = 1 cho tới n <ul> <li>V&ograve;ng lặp for i = 1 tới n <ul> <li>V&ograve;ng lặp for j = 1 tới n <ul> <li>$A^k[i, j] = \text{min}(A^{k - 1}[i, j], A^{k - 1}[i, k] + A^{k - 1}[k, j])$</li> </ul> </li> </ul> </li> </ul> </li> <li>Trả về A</li> </ul> <p>V&iacute; dụ: Triển khai thuật to&aacute;n Floyd-Warshall bằng ng&ocirc;n ngữ lập tr&igrave;nh C.</p> <pre class="language-cpp"><code>#include &lt;stdio.h&gt; #define nV 4 #define INF 999 void print(int a[][nV]); void floy_warshall(int graph[][nV]) { int a[nV][nV], i, j, k; for (i = 0; i &lt; nV; i++) for (j = 0; j &lt; nV; j++) a[i][j] = graph[i][j]; for (k = 0; k &lt; nV; k++) { for (i = 0; i &lt; nV; i++) { for (j = 0; j &lt; nV; j++) { if (a[i][k] + a[k][j] &lt; a[i][j]) a[i][j] = a[i][k] + a[k][j]; } } } print(a); } void print(int a[][nV]) { for (int i = 0; i &lt; nV; i++) { for (int j = 0; j &lt; nV; j++) { if (a[i][j] == INF) printf("%4s", "INF"); else printf("%4d", a[i][j]); } printf("\n"); } } int main() { int graph[nV][nV] = {{0, 3, INF, 5}, {2, 0, INF, 4}, {INF, 1, 0, INF}, {INF, INF, 2, 0}}; floy_warshall(graph); }</code></pre> <p>Kết quả:</p> <div id="urvanov-syntax-highlighter-61089a7ce76f0309241427" class="urvanov-syntax-highlighter-syntax crayon-theme-classic urvanov-syntax-highlighter-font-monaco urvanov-syntax-highlighter-os-pc print-yes notranslate" data-settings=" minimize scroll-mouseover"> <div class="urvanov-syntax-highlighter-main"> <pre class="language-cpp"><code> 0 3 7 5 2 0 6 4 3 1 0 5 5 3 2 0</code></pre> <h2 id="ftoc-heading-3" class="ftwp-heading" style="text-align: justify;">3. Độ phức tạp của thuật to&aacute;n Floyd-Warshall</h2> <h3 style="text-align: justify;">3.1. Độ phức tạp về thời gian</h3> <p style="text-align: justify;">C&oacute; ba v&ograve;ng lặp. Mỗi v&ograve;ng lặp c&oacute; độ phức tạp kh&ocirc;ng đổi. V&igrave; vậy, độ phức tạp về thời gian của thuật to&aacute;n Floyd-Warshall l&agrave; $O(n^3)$</p> <h3 style="text-align: justify;">3.2. Độ phức tạp về kh&ocirc;ng gian</h3> <p style="text-align: justify;">Độ phức tạp về kh&ocirc;ng gian của thuật to&aacute;n Floyd-Warshall l&agrave; $O(n^2)$</p> <h2 id="ftoc-heading-4" class="ftwp-heading" style="text-align: justify;">4. Ứng dụng của thuật to&aacute;n Floyd Warshall</h2> <ul style="text-align: justify;"> <li>Được sử dụng để t&igrave;m đường đi ngắn nhất trong đồ thị c&oacute; hướng.</li> <li>Để t&igrave;m ra ma trận Transitive Closure của đồ thị c&oacute; hướng.</li> <li>Để t&igrave;m nghịch đảo của ma trận thực.</li> <li>Để kiểm tra xem một biểu đồ v&ocirc; hướng c&oacute; phải l&agrave; đồ thị hai ph&iacute;a hay kh&ocirc;ng.</li> </ul> <p style="text-align: justify;">Tr&ecirc;n đ&acirc;y l&agrave; kh&aacute;i niệm v&agrave; v&iacute; dụ cơ bản về thuật to&aacute;n Floyd-Warshall được &aacute;p dụng cho đồ thị đầy. Hy vọng mọi người c&oacute; thể &aacute;p dụng v&agrave;o trong chương tr&igrave;nh của m&igrave;nh. Nếu mọi người c&oacute; đ&oacute;ng g&oacute;p g&igrave; th&ecirc;m th&igrave; c&oacute; thể để c&aacute;c b&igrave;nh luận b&ecirc;n dưới b&agrave;i viết n&agrave;y. Mọi người h&atilde;y tiếp tục theo d&otilde;i c&aacute;c b&agrave;i tiếp theo v&agrave; cập nhật c&aacute;c b&agrave;i mới nhất tr&ecirc;n&nbsp;<a href="../../../">tek4</a>&nbsp;nh&eacute;!</p> </div> </div>