Thuật toán Dijkstra và các cách thực thi

<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ề thuật to&aacute;n Dijkstra với c&aacute;c v&iacute; dụ l&agrave; c&aacute;c h&igrave;nh vẽ minh họa, đoạn giả m&atilde; của thuật to&aacute;n n&agrave;y c&ugrave;ng với c&aacute;c ứng dụng của n&oacute;.</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 Dijkstra cho ph&eacute;p ch&uacute;ng ta t&igrave;m đường đi ngắn nhất giữa hai đỉnh bất kỳ của đồ thị. N&oacute; kh&aacute;c với c&acirc;y khung nhỏ nhất v&igrave; khoảng c&aacute;ch ngắn nhất giữa hai đỉnh c&oacute; thể kh&ocirc;ng bao gồm tất cả c&aacute;c đỉnh của đồ thị.</p> <p style="text-align: justify;">C&aacute;ch thức hoạt động của thuật to&aacute;n như sau:</p> <ul style="text-align: justify;"> <li>Thuật to&aacute;n Dijkstra hoạt động dựa tr&ecirc;n cơ sở bất kỳ đường đi con n&agrave;o từ B tới D của đường đi ngắn nhất từ A đến D giữa c&aacute;c đỉnh A v&agrave; D cũng l&agrave; đường đi ngắn nhất giữa c&aacute;c đỉnh B v&agrave; D.</li> <li>Djikstra đ&atilde; sử dụng thuộc t&iacute;nh n&agrave;y theo hướng ngược lại, tức l&agrave; ch&uacute;ng ta ước t&iacute;nh vượt qua khoảng c&aacute;ch của mỗi đỉnh từ đỉnh đầu ti&ecirc;n. Sau đ&oacute;, ch&uacute;ng ta sẽ truy cập từng n&uacute;t v&agrave; c&aacute;c n&uacute;t l&acirc;n cận của n&oacute; để t&igrave;m đường đi con ngắn nhất đến c&aacute;c n&uacute;t l&acirc;n cận đ&oacute;.</li> <li>Thuật to&aacute;n sử dụng c&aacute;ch tiếp cận tham lam, tức l&agrave; ch&uacute;ng ta sẽ t&igrave;m ra giải ph&aacute;p tốt nhất tiếp theo với hy vọng rằng kết quả cuối c&ugrave;ng l&agrave; giải ph&aacute;p tốt nhất cho to&agrave;n bộ vấn đề.</li> </ul> <h2 id="ftoc-heading-2" class="ftwp-heading" style="text-align: justify;">2. V&iacute; dụ về thuật to&aacute;n</h2> <ul> <li style="text-align: justify;">Giả sử ta c&oacute; một đồ thị chứa c&aacute;c trọng số như sau</li> </ul> <p><img style="width: 100%;" src="../../../public_files/cbd678e5-89f7-4a37-80e9-a13caaae44c2" alt="thuat-toan-dijkstra" /></p> <ul> <li>Chọn một đỉnh bắt đầu v&agrave; g&aacute;n gi&aacute; trị v&ocirc; cực cho tất cả c&aacute;c n&uacute;t kh&aacute;c.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/1dcb308c-931c-4051-a896-f8d67d340790" alt="thuat-toan-dijkstra-2" /></p> <ul> <li>Đi đến từng đỉnh v&agrave; cập nhật độ d&agrave;i đường đi của n&oacute;.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/27745de2-5d9c-428d-b871-cb3a36fc10a1" alt="thuat-toan-dijkstra-3" /></p> <ul> <li>Nếu độ d&agrave;i đường đi của đỉnh liền kề nhỏ hơn độ d&agrave;i đường đi mới, kh&ocirc;ng thực hiện cập nhật cho n&oacute;.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/d5290819-bf91-4a76-a932-494662307d79" alt="thuat-toan-dijkstra-4" /></p> <ul> <li>Kh&ocirc;ng thực hiện cập nhật độ d&agrave;i đường đi của c&aacute;c đỉnh đ&atilde; được truy cập.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/d6382e97-348d-4b94-9a9f-47f8c34a10fc" alt="thuat-toan-dijkstra-5" /></p> <ul> <li>Sau mỗi lần lặp, ch&uacute;ng ta chọn đỉnh chưa được duyệt c&oacute; độ d&agrave;i đường đi nhỏ nhất. V&igrave; vậy, ch&uacute;ng ta sẽ chọn 5 trước 7.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/7c6c70db-683f-439c-b276-a153fb78d382" alt="thuat-toan-dijkstra-6" /></p> <ul> <li>Lưu &yacute; rằng đỉnh ngo&agrave;i c&ugrave;ng b&ecirc;n phải c&oacute; độ d&agrave;i đường đi được cập nhật hai lần.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/a501457c-f6d6-4c90-baa9-0f99b228a609" alt="thuat-toan-dijkstra-7" /></p> <ul> <li>Lặp lại cho đến khi tất cả c&aacute;c đỉnh đ&atilde; được duyệt.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/cb7320ff-ce27-46bd-958b-95fb2f927fda" alt="thuat-toan-dijkstra-8" /></p> <h2 id="ftoc-heading-3" class="ftwp-heading" style="text-align: justify;">3. Đoạn giả m&atilde; cho thuật to&aacute;n</h2> <p style="text-align: justify;">Ch&uacute;ng ta cần duy tr&igrave; khoảng c&aacute;ch đường đi của mỗi đỉnh. Ch&uacute;ng ta c&oacute; thể lưu trữ n&oacute; trong một mảng c&oacute; k&iacute;ch thước v, trong đ&oacute; v l&agrave; số đỉnh.</p> <p style="text-align: justify;">Ch&uacute;ng ta cũng muốn c&oacute; thể đi được con đường ngắn nhất, kh&ocirc;ng chỉ biết độ d&agrave;i của con đường ngắn nhất. Đối với điều n&agrave;y, ch&uacute;ng ta sẽ &aacute;nh xạ mỗi đỉnh với đỉnh được cập nhật lần cuối c&ugrave;ng độ d&agrave;i đường đi của n&oacute;.</p> <p style="text-align: justify;">Sau khi thuật to&aacute;n kết th&uacute;c, ch&uacute;ng ta c&oacute; thể quay ngược lại từ đỉnh đ&iacute;ch đến đỉnh nguồn để t&igrave;m đường đi. Một h&agrave;ng đợi ưu ti&ecirc;n nhỏ nhất c&oacute; thể được sử dụng để nhận đỉnh c&oacute; khoảng c&aacute;ch đường đi nhỏ nhất một c&aacute;ch hiệu quả.</p> <ul style="text-align: justify;"> <li>H&agrave;m dijkstra với tham số đầu v&agrave;o l&agrave; (G, S) <ul> <li>Sử dụng v&ograve;ng lặp for cho mỗi đỉnh V trong G <ul> <li>G&aacute;n khoảng c&aacute;ch[V]&nbsp;<strong>&larr;</strong>&nbsp;gi&aacute; trị v&ocirc; cực</li> <li>G&aacute;n phần trước[V]&nbsp;<strong>&larr;</strong>&nbsp;gi&aacute; trị NULL</li> <li>Nếu V != S, thực hiện th&ecirc;m V v&agrave;o trong h&agrave;ng đợi ưu ti&ecirc;n Q</li> </ul> </li> <li>G&aacute;n khoảng c&aacute;ch[S]&nbsp;<strong>&larr;</strong>&nbsp;0</li> </ul> </li> <li>Trong khi Q kh&ocirc;ng rỗng <ul> <li>G&aacute;n U&nbsp;<strong>&larr;</strong>&nbsp;Gi&aacute; trị MIN được lấy từ Q</li> <li>V&ograve;ng lặp for với mỗi n&uacute;t chưa được duyệt V của U <ul> <li>G&aacute;n khoảng c&aacute;ch tạm thời&nbsp;<strong>&larr;</strong>&nbsp;khoảng c&aacute;ch[U] + trọng số cạnh(U, V)</li> <li>Nếu khoảng c&aacute;ch tạm thời &lt; khoảng c&aacute;ch[V] <ul> <li>G&aacute;n khoảng c&aacute;ch[V]&nbsp;<strong>&larr;</strong>&nbsp;Khoảng c&aacute;ch tạm thời</li> <li>G&aacute;n phần trước[V]&nbsp;<strong>&larr;</strong>&nbsp;U</li> </ul> </li> </ul> </li> </ul> </li> <li>Trả về mảng khoảng c&aacute;ch[], mảng th&agrave;nh phần trước[]</li> </ul> <h2 id="ftoc-heading-4" class="ftwp-heading" style="text-align: justify;">4. Độ phức tạp của thuật to&aacute;n Dijkstra</h2> <ul style="text-align: justify;"> <li>Độ phức tạp về thời gian: $O(E log V)$. Trong đ&oacute;, E l&agrave; số cạnh v&agrave; V l&agrave; số đỉnh.</li> <li>Độ phức tạp về kh&ocirc;ng gian: $O(V)$</li> </ul> <h2 id="ftoc-heading-5" class="ftwp-heading" style="text-align: justify;">5. C&aacute;c ứng dụng của thuật to&aacute;n Dijkstra</h2> <ul style="text-align: justify;"> <li>Được sử dụng để t&igrave;m con đường đi ngắn nhất.</li> <li>Được sử dụng trong c&aacute;c ứng dụng mạng x&atilde; hội.</li> <li>Được ứng dụng trong mạng điện thoại.</li> <li>Được ứng dụng để t&igrave;m c&aacute;c vị tr&iacute; trong bản đồ.</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 Dijkstra. 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>