<p style="text-align: justify;">Python l&agrave; một trong những ng&ocirc;n ngữ lập tr&igrave;nh phổ biến nhất hiện nay b&ecirc;n cạnh Java hay JavaScript. Điều l&agrave;m n&ecirc;n sự phổ biến n&agrave;y của Python l&agrave; do t&iacute;nh chất đơn giản, dễ tiếp cận c&ugrave;ng với khối lượng thư viện đồ sộ cho mọi ứng dụng do đ&oacute; n&oacute; rất hay được d&ugrave;ng để tạo ra c&aacute;c bản thử nghiệm mẫu của ứng dụng, huấn luyện c&aacute;c m&ocirc; h&igrave;nh machine learning, tạo ra c&aacute;c ứng dụng web nhanh ch&oacute;ng dễ d&agrave;ng.&nbsp;</p>
<p style="text-align: justify;">Kh&oacute;a học lập tr&igrave;nh Python cơ bản cung cấp cho người học những kiến thức cơ bản nhất về Python. Đ&acirc;y l&agrave; một kh&oacute;a học với rất nhiều b&agrave;i tập, project dự &aacute;n v&iacute; dụ gi&uacute;p cho người học c&oacute; thể chủ động v&agrave; nắm được c&aacute;ch giải quyết một b&agrave;i to&aacute;n cụ thể bằng ng&ocirc;n ngữ lập tr&igrave;nh m&agrave; cụ thể ở đ&acirc;y l&agrave; ng&ocirc;n ngữ Python. Mục ti&ecirc;u của kh&oacute;a học n&agrave;y l&agrave; gi&uacute;p cho bạn c&oacute; thể lập tr&igrave;nh th&agrave;nh thạo Python một c&aacute;ch cơ bản từ con số 0.&nbsp; Kh&oacute;a học sẽ cung cấp cho bạn c&aacute;c kh&aacute;i niệm cơ bản về biến v&agrave; c&aacute;c kiểu dữ liệu kh&aacute;c nhau trong Python, biết c&aacute;ch sử dụng c&aacute;c h&agrave;m v&agrave; mảng, cũng như vận dụng th&agrave;nh thạo c&aacute;c cấu tr&uacute;c điều khiển để giải quyết c&aacute;c vấn đề lập tr&igrave;nh thực tế.</p>
<h2>Kh&oacute;a học n&agrave;y d&agrave;nh cho ai?</h2>
<ul>
<li style="text-align: justify;">Bạn bắt đầu với lập tr&igrave;nh v&agrave; muốn học lập tr&igrave;nh từ đầu ?</li>
<li style="text-align: justify;">Bạn muốn l&agrave;m quen với Python ?</li>
<li style="text-align: justify;">Bạn muốn tiếp tục để sử dụng th&agrave;nh thạo Python cho c&aacute;c c&ocirc;ng việc kh&aacute;c như trong c&aacute;c lĩnh vực: Machine learning, Lập tr&igrave;nh Web,...?</li>
</ul>
<p style="text-align: justify;">Kh&oacute;a học n&agrave;y l&agrave; d&agrave;nh cho bạn: Đơn giản, dễ hiểu, thực tế, thực h&agrave;nh trực tiếp ngay sau khi học với nhiều ứng dụng. Bạn c&oacute; thể tiếp cận mọi thứ dễ d&agrave;ng v&agrave; hiệu quả hơn với "Lập tr&igrave;nh Python cơ bản" của TEK4.VN.</p>
<h2 style="text-align: justify;">Bạn cần l&agrave;m g&igrave; để bắt đầu?</h2>
<p style="text-align: justify;">Kh&oacute;a học n&agrave;y được thiết kế cho cả những người mới bắt đầu do đ&oacute;, những g&igrave; bạn cần l&agrave;:</p>
<div class="udlite-block-list-item udlite-block-list-item-small udlite-block-list-item-tight udlite-block-list-item-neutral udlite-text-sm">
<ul>
<li class="udlite-block-list-item-content" style="text-align: justify;">Một chiếc m&aacute;y t&iacute;nh (Windows, Mac, hoặc Linux), thậm ch&iacute; một chiếc điện thoại c&oacute; c&agrave;i tr&igrave;nh duyệt Web.</li>
<li class="udlite-block-list-item-content" style="text-align: justify;">KH&Ocirc;NG cần biết trước về Python</li>
<li class="udlite-block-list-item-content" style="text-align: justify;">KH&Ocirc;NG cần bất cứ kinh nghiệm lập tr&igrave;nh n&agrave;o.</li>
<li class="udlite-block-list-item-content" style="text-align: justify;">Bạn chỉ cần chăm chỉ, chịu kh&oacute; v&agrave; l&agrave;m theo đ&uacute;ng tiến độ đề ra trong Kh&oacute;a học.</li>
</ul>
</div>
<h2 style="text-align: justify;">Những c&acirc;u hỏi thường gặp</h2>
<p style="text-align: justify;"><strong>Liệu t&ocirc;i c&oacute; thể kiếm được việc sau khi ho&agrave;n th&agrave;nh kh&oacute;a học n&agrave;y?</strong></p>
<p style="text-align: justify;">Tất nhi&ecirc;n rồi, điều g&igrave; cũng c&oacute; thể nhưng phụ thuộc v&agrave;o cố gắng của bạn. Kh&oacute;a học n&agrave;y bản th&acirc;n n&oacute; chỉ cung cấp những nền tảng cơ bản nhất, c&ograve;n để đi v&agrave;o thực tế s&acirc;u hơn, bạn cần t&igrave;m hiểu v&agrave; l&agrave;m nhiều hơn thế rất nhiều.</p>
<p style="text-align: justify;"><strong>T&ocirc;i sẽ mất bao l&acirc;u để ho&agrave;n th&agrave;nh kh&oacute;a học n&agrave;y?</strong></p>
<p style="text-align: justify;">Điều n&agrave;y phụ thuộc v&agrave;o hai yếu tố:</p>
<ol style="text-align: justify;">
<li>Kiến thức nền tảng của bạn. Chắc chắn việc đ&atilde; l&agrave;m quen với lập tr&igrave;nh v&agrave; một số ng&ocirc;n ngữ lập tr&igrave;nh sẽ gi&uacute;p bạn tiếp cận nhanh kh&oacute;a học n&agrave;y hơn.</li>
<li>Sự tập trung v&agrave; nỗ&nbsp;lực của bạn. Nếu bạn chỉ xem kh&oacute;a học một c&aacute;ch thụ động th&igrave; chắc chắn bạn chỉ mất khoảng chưa đầy một ng&agrave;y l&agrave; c&oacute; thể kết th&uacute;c kh&oacute;a học. Tuy vậy, TEK4.VN kh&ocirc;ng khuyến kh&iacute;ch điều n&agrave;y. Việc xem thụ động chỉ gi&uacute;p bạn lướt qua vấn đề v&agrave; khi gặp một b&agrave;i to&aacute;n thực tế chắc chắn bạn sẽ gặp kh&aacute; nhiều kh&oacute; khăn. Để học tập hiệu quả, bạn n&ecirc;n thực h&agrave;nh, tự suy nghĩ, học một c&aacute;ch chủ động c&aacute;c b&agrave;i tập trước khi xem phần hướng dẫn. Bạn c&agrave;ng chủ động thực h&agrave;nh, luyện tập bao nhi&ecirc;u th&igrave; bạn c&agrave;ng th&agrave;nh thạo bấy nhi&ecirc;u.&nbsp; Trung b&igrave;nh để th&agrave;nh thạo to&agrave;n bộ kh&oacute;a học n&agrave;y sẽ cần bạn đầu tư khoảng 60 giờ. Kh&ocirc;ng qu&aacute; nhiều nếu bạn nghĩ đến viễn cảnh sẽ c&oacute; thể lập tr&igrave;nh một c&aacute;ch th&agrave;nh thạo. Chỉ cần mỗi n&agrave;y bỏ ra khoảng 2 giờ, trong một th&aacute;ng. Kh&ocirc;ng nhiều phải kh&ocirc;ng ạ?</li>
</ol>
<p style="text-align: justify;">Dựa tr&ecirc;n hai yếu tố tr&ecirc;n, chắc hẳn bạn đ&atilde; c&oacute; thể ước đo&aacute;n được cần bao nhi&ecirc;u thời gian v&agrave; sắp xếp thời gian thế n&agrave;o cho hợp l&yacute; rồi chứ?</p>
<p style="text-align: justify;"><strong>T&ocirc;i chưa biết lập tr&igrave;nh, liệu t&ocirc;i c&oacute; thể học được kh&oacute;a Lập tr&igrave;nh Python cơ bản n&agrave;y hay kh&ocirc;ng ?</strong></p>
<p style="text-align: justify;">Kh&oacute;a học n&agrave;y được thiết kế cho người mới bắt đầu từ số 0, chưa c&oacute; bất cứ kh&aacute;i niệm n&agrave;o về lập tr&igrave;nh. Do đ&oacute;, c&aacute;c kh&aacute;i niệm được giải th&iacute;ch kh&aacute; kỹ lưỡng. Điều n&agrave;y sẽ gi&uacute;p bạn kh&ocirc;ng những c&oacute; thể hiểu c&aacute;ch sử dụng c&aacute;c kh&aacute;i niệm n&agrave;y trong Python, m&agrave; c&oacute; thể gi&uacute;p bạn hiểu được kh&aacute;i niệm đ&oacute; c&oacute; &yacute; nghĩa như thế n&agrave;o trong lập tr&igrave;nh n&oacute;i chung.</p>
<p style="text-align: justify;"><strong>Kh&oacute;a học n&agrave;y dạy Python 2 hay Python 3?</strong></p>
<p style="text-align: justify;">Python 3, chắc chắn rồi. Python 2 hiện nay đ&atilde; kh&ocirc;ng c&ograve;n được hỗ trợ cập nhật v&agrave; chuyển dần sang Python 3. Do đ&oacute;, kh&oacute;a học n&agrave;y sẽ hướng đến Python 3.</p>
<p style="text-align: justify;"><strong>T&ocirc;i n&ecirc;n d&ugrave;ng tr&igrave;nh soạn thảo hoặc IDE n&agrave;o trong kh&oacute;a học?</strong></p>
<p style="text-align: justify;">Trong kh&oacute;a học n&agrave;y, ch&uacute;ng ta sử dụng Visual Studio Code. Tuy nhi&ecirc;n, bạn cũng c&oacute; thể sử dụng bất cứ một IDE hoặc tr&igrave;nh soạn thảo n&agrave;o quan thuộc chẳng hạn như: PyCharm, Atom, hay thậm ch&iacute; l&agrave; tr&igrave;nh soạn thảo mặc định IDLE k&egrave;m theo khi c&agrave;i đặt. Tất cả m&atilde; nguồn trong kh&oacute;a học đều c&oacute; thể hoạt động tốt tr&ecirc;n tất cả c&aacute;c m&ocirc;i trường n&agrave;y. Ngo&agrave;i ra, TEK4.VN c&ograve;n cung cấp m&ocirc;i trường soạn thảo v&agrave; bi&ecirc;n dịch trực tiếp phục vụ cho c&aacute;c bạn l&agrave;m b&agrave;i v&agrave; tự động đ&aacute;nh gi&aacute; kết quả trực tuyến ngay ở c&aacute;c b&agrave;i tập. Tr&igrave;nh soạn thảo trực tuyến n&agrave;y sẽ được sử dụng để l&agrave;m c&aacute;c b&agrave;i tập trong kh&oacute;a học.</p>
<p style="text-align: justify;"><strong>L&agrave;m thế n&agrave;o để ho&agrave;n th&agrave;nh kh&oacute;a học n&agrave;y?</strong></p>
<p style="text-align: justify;">Để ho&agrave;n th&agrave;nh kh&oacute;a học n&agrave;y, bạn cần l&agrave;m đầy đủ c&aacute;c b&agrave;i tập dạng lập tr&igrave;nh v&agrave; dạng trắc nghiệm kiến thức (quiz). C&aacute;c b&agrave;i tập n&agrave;y sẽ được chấm tự động trực tuyến v&agrave; phản hồi lại kết quả ngay lập tức đến người học. Điều n&agrave;y sẽ gi&uacute;p bạn biết tiến độ v&agrave; mức độ nắm bắt kiến thức hiện tại của m&igrave;nh để chủ động điều chỉnh ph&ugrave; hợp.</p>
<p style="text-align: justify;"><strong>Nếu c&oacute; thắc mắc hoặc kh&oacute; hiểu liệu t&ocirc;i c&oacute; thể t&igrave;m sự trợ gi&uacute;p ở đ&acirc;u?<br /></strong></p>
<p style="text-align: justify;">Trong qu&aacute; tr&igrave;nh truy cập v&agrave; học tập nếu gặp vấn đề trong việc giải b&agrave;i tập h&atilde;y trao đổi qua cộng đồng <a class="in-cell-link" href="https://www.facebook.com/groups/tek4.vn" target="_blank" rel="noopener">TEK4.VN - Học Lập Tr&igrave;nh Miễn Ph&iacute;</a> để được hỗ trợ giải đ&aacute;p nhanh nhất. C&aacute;c vấn đề kh&aacute;c vui l&ograve;ng nhắn tin trực tiếp <em><strong>Fanpage Facebook:</strong>&nbsp;<a href="https://www.facebook.com/tek4.vn/">TEK4.VN</a></em> để admin giải đ&aacute;p bạn nh&eacute;. Hoặc bạn c&oacute; thể đặt trực tiếp c&aacute;c c&acirc;u hỏi v&agrave;o trong phần b&igrave;nh luận của website.</p>

Lập trình Python cơ bản

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

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