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;
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ế.
<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>
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.
<h2 style="text-align: justify;">Bạn cần l&agrave;m g&igrave; để bắt đầu?</h2>
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;:
<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>
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?
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.
T&ocirc;i sẽ mất bao l&acirc;u để ho&agrave;n th&agrave;nh kh&oacute;a học n&agrave;y?
Điều n&agrave;y phụ thuộc v&agrave;o hai yếu tố:
<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>
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ứ?
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 ?
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.
Kh&oacute;a học n&agrave;y dạy Python 2 hay Python 3?
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.
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?
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.
L&agrave;m thế n&agrave;o để ho&agrave;n th&agrave;nh kh&oacute;a học n&agrave;y?
Để 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.
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? 
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 Fanpage Facebook:&nbsp;<a href="https://www.facebook.com/tek4.vn/">TEK4.VN</a> để 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.

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

Thuật to&aacute;n Johnson l&agrave; một thuật to&aacute;n t&igrave;m đường đi ngắn nhất, được sử dụng để giải quyết tất b&agrave;i to&aacute;n về việc t&igrave;m c&aacute;c cặp cạnh c&oacute; đường đi ngắn nhất. B&agrave;i to&aacute;n t&igrave;m tất cả c&aacute;c cặp đường đi ngắn nhất nhận đầu v&agrave;o l&agrave; một đồ thị c&oacute; c&aacute;c đỉnh v&agrave; c&aacute;c cạnh, v&agrave; n&oacute; đưa ra đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị đ&oacute;. Thuật to&aacute;n Johnson rất giống với thuật to&aacute;n Floyd-Warshall, tuy nhi&ecirc;n, Floyd-Warshall hiệu quả nhất đối với đồ thị đầy (nhiều cặp cạnh), trong khi thuật to&aacute;n Johnson hiệu quả nhất đối với đồ thị thưa (&iacute;t c&aacute;c cạnh).
<h2 id="ftoc-heading-1" class="ftwp-heading" style="text-align: justify;">1. Kh&aacute;i niệm</h2>
L&yacute; do m&agrave; thuật to&aacute;n Johnson tốt hơn cho đồ thị thưa l&agrave; độ phức tạp về thời gian của n&oacute; phụ thuộc v&agrave;o số cạnh trong đồ thị, trong khi của Floyd-Warshall th&igrave; kh&ocirc;ng. Thuật to&aacute;n của Johnson chạy trong khoảng thời gian l&agrave; $O(V^2.log(V) + |V|.|E|)$. V&igrave; vậy, nếu số lượng cạnh nhỏ (tức l&agrave; đồ thị thưa), n&oacute; sẽ chạy nhanh hơn $O(V^3)$&nbsp;so với thuật to&aacute;n Floyd-Warshall.
Thuật to&aacute;n Johnson sử dụng thuật to&aacute;n Bellman-Ford l&agrave;m thuật to&aacute;n con để đ&aacute;nh lại trọng số cho đồ thị đầu v&agrave;o nhằm loại bỏ c&aacute;c cạnh c&oacute; trọng số &acirc;m v&agrave; ph&aacute;t hiện c&aacute;c chu kỳ v&ograve;ng lặp &acirc;m. Với đồ thị mới đ&atilde; được thay đổi n&agrave;y, n&oacute; sẽ sử dụng thuật to&aacute;n đường đi ngắn nhất của Dijkstra để t&iacute;nh đường đi ngắn nhất giữa tất cả c&aacute;c cặp đỉnh. Đầu ra của thuật to&aacute;n sau đ&oacute; l&agrave; tập hợp c&aacute;c đường đi ngắn nhất trong đồ thị ban đầu.
Thuật to&aacute;n của Johnson hoạt động hiệu quả cũng như nhiều thuật t&igrave;m to&aacute;n đường đi ngắn nhất cho đồ thị đầu v&agrave;o, G. Đồ thị n&agrave;y c&oacute; một tập c&aacute;c đỉnh, V, &aacute;nh xạ tới một tập c&aacute;c cạnh, E. Mỗi cạnh, $(u, v)$, c&oacute; một h&agrave;m trọng số $w = \text{distance(u, v)}$. Thuật to&aacute;n của Johnson hoạt động tr&ecirc;n đồ thị c&oacute; hướng, c&oacute; trọng số. N&oacute; cho ph&eacute;p c&aacute;c cạnh c&oacute; trọng số &acirc;m, nhưng kh&ocirc;ng thể c&oacute; chu kỳ trọng số &acirc;m (v&igrave; khi đ&oacute; sẽ kh&ocirc;ng tồn tại đường đi ngắn nhất cho c&aacute;c đỉnh bởi chu kỳ đ&oacute;).
<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 Johnson</h2>
Thuật to&aacute;n Johnson bao gồm ba bước sau:
<ol style="text-align: justify;">
<li>Một đỉnh mới được th&ecirc;m v&agrave;o đồ thị v&agrave; n&oacute; được nối bằng c&aacute;c cạnh c&oacute; trọng số bằng kh&ocirc;ng với tất cả c&aacute;c đỉnh kh&aacute;c trong đồ thị.</li>
<li>Tất cả c&aacute;c cạnh đều đi qua qu&aacute; tr&igrave;nh đ&aacute;nh lại trọng số để loại bỏ c&aacute;c cạnh trọng số &acirc;m.</li>
<li>Đỉnh được th&ecirc;m v&agrave;o từ bước 1 bị loại bỏ v&agrave; thuật to&aacute;n Dijkstra được chạy tr&ecirc;n mọi n&uacute;t trong biểu đồ.</li>
</ol>
Ba bước n&agrave;y c&oacute; thể được biểu diễn trong h&igrave;nh b&ecirc;n dưới. H&igrave;nh (a) cho thấy bước 1. H&igrave;nh (b) cho thấy bước 2. H&igrave;nh (c) &ndash; (g) cho thấy bước 3, thuật to&aacute;n Dijkstra đang được chạy tr&ecirc;n mỗi đỉnh trong số 5 đỉnh của đồ thị.
<img style="width: 100%;" src="../../../public_files/e206ea8e-7b06-48cf-9516-993ed78b5fde" alt="thuat-toan-johnson" />
Đoạn giả m&atilde; của giải thuật được triển khai như sau:
<ul style="text-align: justify;">
<li>H&agrave;m Johnson(G)
<ul>
<li>1.</li>
<li>Tạo G` trong đ&oacute; G`.V = G.V &cup; {s},
<ul>
<li>G`.E = G.E &cup; ((s, u) với u trong G.V, v&agrave;</li>
<li>Trọng số(s, u) = 0 với u trong G.V</li>
</ul>
</li>
<li>2.</li>
<li>Nếu Bellman-Ford(s) == false
<ul>
<li>Trả về v&agrave; đưa ra th&ocirc;ng b&aacute;o</li>
</ul>
</li>
<li>Nếu kh&ocirc;ng:
<ul>
<li>Với mỗi đỉnh v trong G`.V:
<ul>
<li>h(v) = Khoảng c&aacute;ch(s, v) được t&iacute;nh bởi thuật to&aacute;n Bellman-Ford</li>
</ul>
</li>
<li>Với mỗi cạnh (u, v) trong G`.E:
<ul>
<li>Trọng số`(u, v) = Trọng số(u, v) + h(u) &ndash; h(v)</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li>3.
<ul>
<li>D = ma trận mới bao gồm c&aacute;c khoảng c&aacute;ch được khởi tạo với gi&aacute; trị v&ocirc; cực</li>
<li>Với mỗi đỉnh u trong G.V:
<ul>
<li>Thực hiện Dijkstra(G, Trọng số`, u) để t&igrave;m khoảng c&aacute;ch`(u, v) cho tất cả c&aacute;c v trong G.v</li>
<li>Với mỗi đỉnh v trong G.V:
<ul>
<li>D_(u, v) = khoảng c&aacute;ch`(u, v) + h(v) &ndash; h(u)</li>
</ul>
</li>
</ul>
</li>
<li>Trả về D</li>
</ul>
</li>
</ul>
Cụ thể về c&aacute;c bước của thuật to&aacute;n được m&ocirc; tả như sau:
<ul>
<li style="text-align: justify;">Bước 1: Th&ecirc;m một đỉnh cơ sở
<ul>
<li style="text-align: justify;">Phần đầu ti&ecirc;n của thuật to&aacute;n kh&aacute; đơn giản. Th&ecirc;m một đỉnh mới, s, v&agrave;o đồ thị v&agrave; kết nối n&oacute; với tất cả c&aacute;c đỉnh kh&aacute;c c&oacute; cạnh trọng số bằng 0.</li>
</ul>
</li>
</ul>
<img style="width: 100%;" src="../../../public_files/5956380a-44eb-4656-abf4-7a5e278e3e36" alt="thuat-toan-johnson-2" />
<ul>
<li style="text-align: justify;">Bước 2: Đ&aacute;nh lại trọng số cho c&aacute;c cạnh
<ul>
<li>Đ&aacute;nh lại trọng số c&oacute; lẽ l&agrave; phần mới lạ nhất của thuật to&aacute;n n&agrave;y. Kh&aacute;i niệm cơ bản l&agrave;: nếu tất cả c&aacute;c cạnh trong đồ thị đều kh&ocirc;ng &acirc;m, th&igrave; việc thực hiện thuật to&aacute;n Dijkstra tr&ecirc;n mọi đỉnh l&agrave; c&aacute;ch nhanh nhất để giải b&agrave;i to&aacute;n đường đi ngắn nhất của tất cả c&aacute;c cặp. Tuy nhi&ecirc;n, nếu một số cạnh c&oacute; trọng số &acirc;m, ch&uacute;ng ta c&oacute; thể đ&aacute;nh trọng số lại cho ch&uacute;ng để giữ nguy&ecirc;n định nghĩa sau.</li>
<li>Đ&aacute;nh lại trọng số l&agrave; một qu&aacute; tr&igrave;nh m&agrave; trọng số của cạnh được thay đổi để thỏa m&atilde;n hai thuộc t&iacute;nh sau:</li>
<li>Đối với tất cả c&aacute;c cặp đỉnh u, v trong đồ thị, nếu một đường đi n&agrave;o đ&oacute; l&agrave; đường đi ngắn nhất giữa c&aacute;c đỉnh đ&oacute; trước khi đ&aacute;nh lại trọng số th&igrave; n&oacute; cũng phải l&agrave; đường đi ngắn nhất giữa c&aacute;c đỉnh đ&oacute; sau đ&aacute;nh lại trọng số.</li>
<li>Đối với tất cả c&aacute;c cạnh, (u, v), trong đồ thị, trọng số (u, v) phải kh&ocirc;ng &acirc;m.</li>
<li>Bước n&agrave;y sử dụng thuật to&aacute;n Bellman-Ford để gi&uacute;p đ&aacute;nh lại trọng số cho c&aacute;c cạnh. Bằng c&aacute;ch sử dụng Bellman-Ford trong bước n&agrave;y, thuật to&aacute;n của Johnson cũng c&oacute; thể ph&aacute;t hiện c&aacute;c chu kỳ trọng lượng &acirc;m, một thuộc t&iacute;nh của Bellman-Ford.</li>
</ul>
</li>
<li style="text-align: justify;">Bước 3: T&igrave;m tất cả c&aacute;c cặp đường đi ngắn nhất
<ul>
<li style="text-align: justify;">Cuối c&ugrave;ng, thuật to&aacute;n Dijkstra được chạy tr&ecirc;n tất cả c&aacute;c đỉnh để t&igrave;m đường đi ngắn nhất. Điều n&agrave;y c&oacute; thể thực hiện được v&igrave; c&aacute;c trọng số đ&atilde; được chuyển đổi th&agrave;nh c&aacute;c trọng số kh&ocirc;ng &acirc;m. Tuy nhi&ecirc;n, điều quan trọng l&agrave; phải chuyển đổi c&aacute;c trọng số đường đi n&agrave;y trở lại th&agrave;nh c&aacute;c trọng số đường đi ban đầu để trọng số đường đi ch&iacute;nh x&aacute;c được trả về khi kết th&uacute;c thuật to&aacute;n. Điều n&agrave;y được thực hiện ở cuối thuật to&aacute;n bằng c&aacute;ch đảo ngược qu&aacute; tr&igrave;nh đ&aacute;nh lại trọng số một c&aacute;ch đơn giản. Th&ocirc;ng thường, một cấu tr&uacute;c dữ liệu như một ma trận được trả về. Tại mọi &ocirc; i, j của ma trận l&agrave; đường đi ngắn nhất từ đỉnh i đến đỉnh j.</li>
</ul>
</li>
</ul>
<h2 id="ftoc-heading-3" class="ftwp-heading" style="text-align: justify;">3. Độ phức tạp của thuật to&aacute;n</h2>
Bước đầu ti&ecirc;n của thuật to&aacute;n chạy trong thời gian $O(V)$ v&igrave; n&oacute; cần tạo một cạnh mới cho tất cả c&aacute;c đỉnh trong đồ thị. Bước thứ hai của thuật to&aacute;n, Bellman-Ford, chạy trong thời gian $O(V E)$, Bellman-Ford cũng vậy. Qu&aacute; tr&igrave;nh x&aacute;c định lại trọng số của đồ thị chạy trong c&ugrave;ng một thời gian tương tự.
Bước cuối c&ugrave;ng của thuật to&aacute;n l&agrave; thuật to&aacute;n Dijkstra chạy tr&ecirc;n tất cả c&aacute;c đỉnh V. Sử dụng một đống Fibonacci, mỗi lần lặp lại n&agrave;y mất $O(Vlog(V) + E)$ thời gian để ho&agrave;n th&agrave;nh với tổng độ phức tạp l&agrave; $O(V^2log(V) + VE)$
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 Johnson. 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;!

Thuật toán Johnson cho đồ thị thưa