Please or Register to create posts and topics.

Các thuật toán về tìm đường đi ngắn nhất

Các thuật toán về tìm đường đi ngắn nhất

Các thuật toán về tìm đường đi ngắn nhất

Tác giả:

  • Trần Hoài An - THPT Hoàng Lê Kha, Tây Ninh

Giới thiệu

Bài toán tìm đường đi ngắn nhất trên đồ thị là một trong những bài toán đa dạng, có nhiều ứng dụng thực tế (như trong Google Maps, hay các bài toán networking, …). Các dạng bài về tìm đường đi ngắn nhất cũng thường xuyên có mặt trong các kì thi lập trình.

Bài viết này sẽ giới thiệu ba thuật toán cơ bản của dạng bài tìm đường đi ngắn nhất:

  • Thuật toán Bellman - Ford.
  • Thuật toán Dijkstra.
  • Thuật toán Floyd-Warshall (còn gọi là thuật toán Floyd).

Cần lưu ý rằng, có một thuật toán thông dụng khác cũng có tên thường gọi là thuật toán Floyd, dùng để tìm chu trình trong đồ thị có hướng. Bài viết này sẽ chỉ đề cập đến thuật toán tìm đường đi ngắn nhất.

1. Thuật toán Bellman - Ford

Thuật toán Bellman-Ford dùng để giải quyết bài toán đường đi ngắn nhất một nguồn (Single-source shortest path), đồ thị có thể có trọng số âm.

Bài toán.

Cho đồ thị có hướng <span id="MathJax-Element-1-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N">NN đỉnh và <span id="MathJax-Element-2-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="M">MM cạnh, và một đỉnh nguồn là đỉnh <span id="MathJax-Element-3-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S">SS. Mỗi cạnh có trọng số nguyên. Trọng số này có thể âm hoặc dương hoặc bằng 0. Với mỗi đỉnh <span id="MathJax-Element-4-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu từ <span id="MathJax-Element-5-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="1">11 đến <span id="MathJax-Element-6-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N">NN. Yêu cầu xuất kết quả tại mỗi đỉnh <span id="MathJax-Element-7-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu như sau:

  1. Nếu không tồn tại đường đi từ <span id="MathJax-Element-8-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S">SS đến <span id="MathJax-Element-9-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu thì in ra: Impossible
  2. Nếu tồn tại đường đi từ <span id="MathJax-Element-10-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S">SS đến <span id="MathJax-Element-11-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu nhưng không có đường đi ngắn nhất in ra: -Infinity
  3. Trường hợp còn lại in ra đường đi ngắn nhất từ <span id="MathJax-Element-12-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S">SS đến <span id="MathJax-Element-13-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu.

Input: Dòng đầu tiên gồm 3 số nguyên <span id="MathJax-Element-14-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N,M,S">N,M,SN,M,S. <span id="MathJax-Element-15-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="M">MM dòng tiếp theo, mỗi dòng gồm ba số nguyên <span id="MathJax-Element-16-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u,v,Wu,v">u,v,Wu,vu,v,Wu,v biểu diễn một cạnh một chiều từ <span id="MathJax-Element-17-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu đến <span id="MathJax-Element-18-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="v">vv với trọng số là <span id="MathJax-Element-19-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="Wu,v">Wu,vWu,v.

Output: gồm <span id="MathJax-Element-20-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N">NN dòng cho biết đường đi ngắn nhất từ đỉnh <span id="MathJax-Element-21-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S">SS đến các đỉnh từ <span id="MathJax-Element-22-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="0">00 đến <span id="MathJax-Element-23-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N−1">N1N−1

Giới hạn bài toán : <span id="MathJax-Element-24-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="1≤N≤1000,1≤M≤5000">1N1000,1M50001≤N≤1000,1≤M≤5000

Sample Input

7 6 4
0 1 7
2 0 1
1 2 -9
2 5 1000
3 0 7
4 3 3

Sample Output

-Infinity
-Infinity
-Infinity
3
0
-Infinity
Impossible

Khái niệm về chu trình âm

  • Chu trình âm là một chu trình trong đó tổng trọng số các cạnh là số âm. Ví dụ trong hình dưới, ta có một chu trình âm <span id="MathJax-Element-25-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="0→1→2">0120→1→2 có tổng trọng số là <span id="MathJax-Element-26-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="7−9+1=−1">79+1=17−9+1=−1

  • Nếu trên đường đi từ <span id="MathJax-Element-27-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu đến <span id="MathJax-Element-28-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="v">vv chứa chu trình âm thì độ dài đường đi ngắn nhất từ <span id="MathJax-Element-29-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu đến <span id="MathJax-Element-30-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="v">vv sẽ là <span id="MathJax-Element-31-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="−∞">−∞. Vì vậy nên sự xuất hiện của chu trình âm trong đồ thị sẽ khiến một số cặp đỉnh không tồn tại đường đi ngắn nhất (chỉ tồn tại đường đi có độ dài âm vô cực).
    • Ví dụ: Ở đồ thị trên, đường đi ngắn nhất từ <span id="MathJax-Element-32-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="4">44 đến <span id="MathJax-Element-33-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="5">55 sẽ có cách đi là vô hạn lần qua chu trình âm đã nhắc đến, sau đó mới đi đến <span id="MathJax-Element-34-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="5">55. Như vậy không có đường đi ngắn nhất.

Ý tưởng của thuật toán.

Xét trường hợp đơn giản hơn, khi đồ thị không có trọng số âm (tức đường đi ngắn nhất luôn tồn tại).

Thuật toán Bellman-Ford sẽ lặp nhiều lần. Ở mỗi vòng lặp, ta sẽ đi qua tất cả các cạnh <span id="MathJax-Element-35-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="(u,v)">(u,v)(u,v) trên đồ thị, so sánh đường đi <span id="MathJax-Element-36-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S→v">SvS→v đã tìm được với đường đi <span id="MathJax-Element-37-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S→u→v">SuvS→u→v

  • Ví dụ đồ thị sau:

  • Giả sử ta tìm được đường đi từ <span id="MathJax-Element-38-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="1→3">131→3 có độ dài là <span id="MathJax-Element-39-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="4">44, và đường đi từ <span id="MathJax-Element-40-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="1→2">121→2 có độ dài là <span id="MathJax-Element-41-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="2">22. Như vậy ta có thể sử dụng cạnh <span id="MathJax-Element-42-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="(2,3)">(2,3)(2,3) để nối dài đường đi <span id="MathJax-Element-43-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="1→2">121→2 thành <span id="MathJax-Element-44-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="1→2→3">1231→2→3 có độ dài bằng <span id="MathJax-Element-45-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="3">33, tốt hơn đường đi trực tiếp <span id="MathJax-Element-46-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="1→3">131→3 ta đã tìm được.

Có thể chứng minh được rằng, vòng lặp trên cần thực hiện <span id="MathJax-Element-47-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N−1">N1N−1 lần, mỗi lần đi qua toàn bộ <span id="MathJax-Element-48-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="M">MM cạnh, là sẽ đủ để tìm đường đi ngắn nhất.

  • Chứng minh: Nhận xét rằng một đường đi ngắn nhất bất kì sẽ không có đỉnh nào được đi lại quá một lần. Như vậy một đường đi ngắn nhất sẽ không có quá <span id="MathJax-Element-49-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N−1">N1N−1 cạnh. Việc thực hiện phép tính <span id="MathJax-Element-50-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="Dv=Du+Wu,v">Dv=Du+Wu,vDv=Du+Wu,v cũng đồng nghĩa với thêm một cạnh <span id="MathJax-Element-51-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u→v">uvu→v vào hành trình đi từ <span id="MathJax-Element-52-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="s">ss đến <span id="MathJax-Element-53-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="v">vv. Vậy một <span id="MathJax-Element-54-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="Du">DuDu chỉ có thể được tối ưu tối đa <span id="MathJax-Element-55-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N−1">N1N−1 lần, và từ lần thứ <span id="MathJax-Element-56-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N">NN trở đi sẽ không thể tối ưu hơn được nữa.

Cài Đặt

Ở thuật toán này, đồ thị thường được lưu ở dạng danh sách cạnh.

  • Định nghĩa <span id="MathJax-Element-57-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="W[u,v]">W[u,v]W[u,v] là trọng số cạnh nối từ đỉnh <span id="MathJax-Element-58-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu đến đỉnh <span id="MathJax-Element-59-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="v">vv (nếu có).

  • Định nghĩa mảng <span id="MathJax-Element-60-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D[u]">D[u]D[u] là đường đi ngắn nhất từ <span id="MathJax-Element-61-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="s→u">sus→u. Ban đầu, chưa có đường đi nào, <span id="MathJax-Element-62-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D[u]=∞">D[u]=D[u]=∞ với mọi <span id="MathJax-Element-63-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu, ngoại trừ <span id="MathJax-Element-64-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D[s]=0">D[s]=0D[s]=0.
    • Nếu cần tìm lại chính đường đi ngắn nhất, ta có thể định nghĩa thêm một mảng truy vết <span id="MathJax-Element-65-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="trace[u]">trace[u]trace[u]. Ban đầu mọi <span id="MathJax-Element-66-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="trace[u]">trace[u]trace[u] bằng <span id="MathJax-Element-67-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="−1">1−1 nghĩa là chưa có đường đi.
  • Thực hiện <span id="MathJax-Element-68-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N−1">N1N−1 lần: Xét lần lượt các cạnh <span id="MathJax-Element-69-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="(u,v)">(u,v)(u,v) trong đồ thị. Nếu <span id="MathJax-Element-70-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D[u]+W[u,v]&lt;D[v]">D[u]+W[u,v]<D[v]D[u]+W[u,v]<D[v], cập nhật <span id="MathJax-Element-71-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D[v]=D[u]+W[u,v])">D[v]=D[u]+W[u,v])D[v]=D[u]+W[u,v]), đồng thời cập nhật <span id="MathJax-Element-72-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="trace[v]=u">trace[v]=utrace[v]=u.

  • Độ phức tạp: Ta có một vòng lặp được thực hiện <span id="MathJax-Element-73-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N−1">N1N−1 lần, mỗi lần lặp ta sẽ xử lí tất cả các cạnh trong đồ thị, như vậy độ phức tạp của thuật toán là <span id="MathJax-Element-74-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="O(N∗M)">O(NM)O(N∗M).

Code:

const long long INF = 2000000000000000000LL;
struct Edge {
    int u, v;
    long long w; // cạnh từ u đến v, trọng số w
};
void bellmanFord(int n, int S, vector<Edge> &e, vector<long long> &D, vector<int> &trace) {
    // e: danh sách cạnh
    // n: số đỉnh
    // S: đỉnh bắt đầu
    // D: độ dài đường đi ngắn nhất
    // trace: mảng truy vết đường đi
    // INF nếu không có đường đi
    // -INF nếu có đường đi âm vô tận
    D.resize(n, INF);
    trace.resize(n, -1);

    D[S] = 0;
    for(int T = 1; T < n; T++) {
        for (auto E : e) {
            int u = E.u;
            int v = E.v;
            long long w = E.w;
            if (D[u] != INF && D[v] > D[u] + w) {
                D[v] = D[u] + w;
                trace[v] = u;
            }
        }
    }
}

Tìm lại đường đi ngắn nhất

Thao tác tìm đường đi ngắn nhất từ <span id="MathJax-Element-75-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S">SS đến <span id="MathJax-Element-76-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu khá đơn giản, ta sẽ bắt đầu từ đỉnh <span id="MathJax-Element-77-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu, sau đó truy vết theo mảng <span id="MathJax-Element-78-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="trace">tracetrace ngược về <span id="MathJax-Element-79-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S">SS.

vector<int> trace_path(vector<int> &trace, int S, int u) {
    if (u != S && trace[u] == -1) return vector<int>(0); // không có đường đi

    vector<int> path;
    while (u != -1) { // truy vết ngược từ u về S
        path.push_back(u);
        u = trace[u];
    }
    reverse(path.begin(), path.end()); // cần reverse vì đường đi lúc này là từ u về S
    
    return path;
}

Các trường hợp có chu trình âm

Thuật toán Bellman-Ford có thể xử lí được thêm trường hợp nhận biết chu trình âm, cũng như nhận biết nếu không tồn tại đường đi ngắn nhất đến một đỉnh.

Nhận biết đường đi âm vô cực

  • Nhận xét tiếp rằng, ta có thể chạy vòng quanh chu trình âm liên tục để được đường đi ngắn hơn. Như vậy thuật toán Bellman-Ford ở vòng lặp thứ <span id="MathJax-Element-80-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N">NN trở đi vẫn sẽ liên tục tối ưu được đường đi, thay vì dừng lại ở lần thứ <span id="MathJax-Element-81-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N−1">N1N−1.
    • Ta chỉ cần chạy thuật toán Bellman-Ford thêm một lần nữa với <span id="MathJax-Element-82-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N">NN vòng lặp, những đỉnh nào vẫn còn tối ưu được ở lần chạy thứ hai sẽ tối ưu được mãi mãi, và đó là các đỉnh không tồn tại đường đi ngắn nhất.

Code:

// sau khi chạy xong N-1 vòng lặp Bellman-Ford 
for(int T = 0; T < n; T++){
    for (auto E : e) {
        int u = E.u;
        int v = E.v;
        long long w = E.w;
        if (D[u] != INF && D[v] > D[u] + w) {
            // vẫn còn tối ưu được --> âm vô cực
            D[v] = -INF;
            trace[v] = u;
        }
    }
}

Tìm chu trình âm

Một số bài toán có thể yêu cầu ta tìm một chu trình âm bất kì trong đồ thị. Ta có thể chỉnh sửa thuật toán Bellman-Ford lại như sau:

  • Thay vì chạy <span id="MathJax-Element-83-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N">NN vòng lặp Bellman-Ford như trường hợp trên, ta chỉ cần chạy một vòng lặp. Như vậy là đủ để phát hiện ít nhất một đỉnh có đường đi bằng <span id="MathJax-Element-84-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="−∞">−∞ (nếu có).
  • Tiến hành truy vết: Bắt đầu từ đỉnh <span id="MathJax-Element-85-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu bất kì có đường đi bằng <span id="MathJax-Element-86-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="−∞">−∞, ta sẽ truy vết theo mảng <span id="MathJax-Element-87-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="trace">tracetrace:
    • Trước hết gán <span id="MathJax-Element-88-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u=trace[u]">u=trace[u]u=trace[u] đủ <span id="MathJax-Element-89-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N">NN lần.
      • Mục đích của bước này là để <span id="MathJax-Element-90-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu chắc chắn thuộc chu trình âm. Ban đầu có thể đỉnh <span id="MathJax-Element-91-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu có đường đi bằng <span id="MathJax-Element-92-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="−∞">−∞ nhưng chưa chắc thuộc chu trình âm. Ví dụ trường hợp sau:

      Ở đây, từ <span id="MathJax-Element-93-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="0">00 đến <span id="MathJax-Element-94-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="1">11 có độ dài đường đi ngắn nhất bằng <span id="MathJax-Element-95-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="−∞">−∞, tuy nhiên đỉnh <span id="MathJax-Element-96-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="1">11 lại không thuộc chu trình âm nào.

    • Sau đó, <span id="MathJax-Element-97-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu sẽ thuộc một chu trình âm. Ta chỉ cần truy vết đỉnh <span id="MathJax-Element-98-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu theo mảng <span id="MathJax-Element-99-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="trace">tracetrace cho đến khi gặp lại chính nó, sẽ được một chu trình.
  • Chu trình vừa truy vết chính là một chu trình âm của đồ thị. Lưu ý ta vẫn phải đảo ngược kết quả truy vết, vì ta đang truy vết ngược so với đồ thị gốc.
bool findNegativeCycle(int n, vector<long long> &D, vector<int> &trace, vector<int> &negCycle) {
    // mảng D và trace đã được chạy qua thuật toán Bellman-Ford
    int negStart = -1; // đỉnh bắt đầu
    for (auto E : e) {
        int u = E.u;
        int v = E.v;
        long long w = E.w;
        if (D[u] != INF && D[v] > D[u] + w) {
            D[v] = -INF; 
            trace[v] = u;
            negStart = v; // đã tìm thấy -INF
        }
    }

    if (negStart == -1) return false; // không có chu trình âm

    int u = negStart;
    for (int i = 0; i < n; i++) {
        u = trace[u]; // đưa u về chu trình âm
    }

    negCycle = vector<int>(1, u);
    for (int v = trace[u]; v != u; v = trace[u]) {
        negCycle.push_back(v); // truy vết một vòng
    }
    reverse(negCycle.begin(), negCycle.end());
    
    return true;
}

2. Thuật toán Dijkstra

Thuật toán Dijkstra dùng để giải quyết bài toán đường đi ngắn nhất một nguồn (Single-source shortest path), đồ thị trọng số không âm.

Bài toán.

Cho một đồ thị có hướng với <span id="MathJax-Element-100-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N">NN đỉnh (được đánh số từ <span id="MathJax-Element-101-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="0">00 đến <span id="MathJax-Element-102-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N−1">N1N−1), <span id="MathJax-Element-103-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="M">MM cạnh có hướng, có trọng số, và một đỉnh nguồn <span id="MathJax-Element-104-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S">SSTrọng số của tất cả các cạnh đều không âm. Yêu cầu tìm ra đường đi ngắn nhất từ đỉnh <span id="MathJax-Element-105-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S">SS tới tất cả các đỉnh còn lại (hoặc cho biết nếu không có đường đi).

Sample Input

7 8 0
0 2 7
0 1 1
0 3 4
2 5 8
5 3 3
4 5 6
1 4 3
2 4 3

Sample Output

0
1
7
4
4
10
-1

Hình ảnh của Test ví dụ. Ở đồ thị này, đỉnh nguồn là đỉnh <span id="MathJax-Element-106-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="0">00, đường đi ngắn nhất từ <span id="MathJax-Element-107-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="0">00 đến các đỉnh <span id="MathJax-Element-108-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="0">00 đến <span id="MathJax-Element-109-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="5">55 là <span id="MathJax-Element-110-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="[0,1,7,4,4,10]">[0,1,7,4,4,10][0,1,7,4,4,10]. Riêng đỉnh <span id="MathJax-Element-111-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="6">66 không có đường đi đến.

Ý tưởng của thuật toán.

Giống như thuật toán Bellman-Ford, thuật toán Dijkstra cũng tối ưu hóa đường đi bằng cách xét các cạnh <span id="MathJax-Element-112-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="(u,v)">(u,v)(u,v), so sánh hai đường đi <span id="MathJax-Element-113-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S→v">SvS→v sẵn có với đường đi <span id="MathJax-Element-114-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S→u→v">SuvS→u→v.

Thuật toán hoạt động bằng cách duy trì một tập hợp các đỉnh trong đó ta đã biết chắc chắn đường đi ngắn nhất. Mỗi bước, thuật toán sẽ chọn ra một đỉnh <span id="MathJax-Element-115-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu mà chắc chắn sẽ không thể tối ưu hơn nữa, sau đó tiến hành tối ưu các đỉnh <span id="MathJax-Element-116-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="v">vv khác dựa trên các cạnh <span id="MathJax-Element-117-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="(u,v)">(u,v)(u,v) đi ra từ đỉnh <span id="MathJax-Element-118-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu. Sau <span id="MathJax-Element-119-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N">NN bước, tất cả các đỉnh đều sẽ được chọn, và mọi đường đi tìm được sẽ là ngắn nhất.

Cụ thể hơn, thuật toán sẽ duy trì đường đi ngắn nhất đến tất cả các đỉnh. Ở mỗi bước, chọn đường đi <span id="MathJax-Element-120-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S→u">SuS→u có tổng trọng số nhỏ nhất trong tất cả các đường đi đang được duy trì. Sau đó tiến hành tối ưu các đường đi <span id="MathJax-Element-121-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S→v">SvS→v bằng cách thử kéo dài thành <span id="MathJax-Element-122-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S→u→v">SuvS→u→v như đã mô tả trên.

Minh họa thuật toán

Ta sẽ minh họa thuật toán bằng một đồ thị như hình. Định nghĩa:

  • <span id="MathJax-Element-123-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="Du">DuDu là đường đi ngắn nhất từ đỉnh nguồn đên đỉnh <span id="MathJax-Element-124-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu đã tìm được.
  • <span id="MathJax-Element-125-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="Pu">PuPu nhận hai giá trị <span id="MathJax-Element-126-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="true">truetrue, <span id="MathJax-Element-127-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="false">falsefalse cho biết đỉnh <span id="MathJax-Element-128-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="Pu">PuPu đã được chọn để tối ưu chưa.

Đỉnh được tô đen (đỉnh 0) sẽ là đỉnh nguồn.

Ban đầu, <span id="MathJax-Element-129-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D=[0,∞,∞,∞]">D=[0,,,]D=[0,∞,∞,∞], <span id="MathJax-Element-130-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="P=[false,false,false,false]">P=[false,false,false,false]P=[false,false,false,false]

  • Bước 1: Thuật toán sẽ chọn đỉnh <span id="MathJax-Element-131-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="0">00, vì <span id="MathJax-Element-132-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D0=0">D0=0D0=0 là nhỏ nhất thỏa mãn <span id="MathJax-Element-133-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="P0=false">P0=falseP0=false. Tiến hành tối ưu các cạnh đi ra:
    • Cạnh <span id="MathJax-Element-134-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="(0,2)">(0,2)(0,2): cập nhật <span id="MathJax-Element-135-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D2=min(D2,D0+W0,2)=min(∞,0+1)=1">D2=min(D2,D0+W0,2)=min(,0+1)=1D2=min(D2,D0+W0,2)=min(∞,0+1)=1
    • Cạnh <span id="MathJax-Element-136-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="(0,3)">(0,3)(0,3): cập nhật <span id="MathJax-Element-137-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D3=min(D3,D0+W0,3)=min(∞,0+4)=4">D3=min(D3,D0+W0,3)=min(,0+4)=4D3=min(D3,D0+W0,3)=min(∞,0+4)=4

Sau bước này, <span id="MathJax-Element-138-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D=[0,∞,1,4]">D=[0,,1,4]D=[0,∞,1,4], <span id="MathJax-Element-139-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="P=[true,false,false,false]">P=[true,false,false,false]P=[true,false,false,false]

  • Bước 2: thuật toán sẽ chọn ra đỉnh <span id="MathJax-Element-140-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="2">22, có <span id="MathJax-Element-141-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D2=1">D2=1D2=1 là nhỏ nhất thỏa mãn <span id="MathJax-Element-142-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="P2=false">P2=falseP2=false. Tiến hành tối ưu các cạnh đi ra:
    • Cạnh <span id="MathJax-Element-143-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="(2,1)">(2,1)(2,1): cập nhật <span id="MathJax-Element-144-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D1=min(D1,D2+W2,1)=min(∞,1+3)=4">D1=min(D1,D2+W2,1)=min(,1+3)=4D1=min(D1,D2+W2,1)=min(∞,1+3)=4
    • Cạnh <span id="MathJax-Element-145-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="(2,3)">(2,3)(2,3): cập nhật <span id="MathJax-Element-146-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D3=min(D3,D2+W2,3)=min(4,1+2)=3">D3=min(D3,D2+W2,3)=min(4,1+2)=3D3=min(D3,D2+W2,3)=min(4,1+2)=3

Sau bước này, <span id="MathJax-Element-147-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D=[0,4,1,3]">D=[0,4,1,3]D=[0,4,1,3], <span id="MathJax-Element-148-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="P=[true,false,true,false]">P=[true,false,true,false]P=[true,false,true,false]

  • Bước 3: thuật toán sẽ chọn ra đỉnh <span id="MathJax-Element-149-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="3">33, có <span id="MathJax-Element-150-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D3=1">D3=1D3=1 là nhỏ nhất thỏa mãn <span id="MathJax-Element-151-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="P3=false">P3=falseP3=false. Tiến hành tối ưu các cạnh đi ra:
    • Cạnh <span id="MathJax-Element-152-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="(3,1)">(3,1)(3,1): cập nhật <span id="MathJax-Element-153-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D1=min(D1,D3+W3,1)=min(4,3+2)=4">D1=min(D1,D3+W3,1)=min(4,3+2)=4D1=min(D1,D3+W3,1)=min(4,3+2)=4

Sau bước này, <span id="MathJax-Element-154-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D=[0,4,1,3]">D=[0,4,1,3]D=[0,4,1,3], <span id="MathJax-Element-155-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="P=[true,false,true,true]">P=[true,false,true,true]P=[true,false,true,true]

  • Bước 4: thuật toán sẽ chọn đỉnh <span id="MathJax-Element-156-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="1">11. Không có cạnh nào đi ra.

Đến đây, tất cả các đỉnh đều đã được đánh dấu. Thuật toán kết thúc. Đường đi ngắn nhất tìm được từ đỉnh <span id="MathJax-Element-157-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="0">00 là <span id="MathJax-Element-158-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D=[0,4,1,3]">D=[0,4,1,3]D=[0,4,1,3].

Cài đặt

Ở thuật toán này, ta sẽ lưu đồ thị dưới dạng danh sách kề. Ta định nghĩa như sau:

  • <span id="MathJax-Element-159-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D[u]">D[u]D[u] là đường đi ngắn nhất từ <span id="MathJax-Element-160-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="s→u">sus→u. Ban đầu khởi tạo <span id="MathJax-Element-161-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D[u]=∞">D[u]=D[u]=∞ với mọi <span id="MathJax-Element-162-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu, riêng <span id="MathJax-Element-163-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D[s]=0">D[s]=0D[s]=0.
    • Cũng như thuật toán Bellman-Ford, ta có thể định nghĩa thêm mảng <span id="MathJax-Element-164-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="trace">tracetrace để truy vết đường đi nếu cần.
  • <span id="MathJax-Element-165-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="W[u,v]">W[u,v]W[u,v] là trọng số cạnh trên đường đi từ <span id="MathJax-Element-166-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u→v">uvu→v.
  • <span id="MathJax-Element-167-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="P[u]">P[u]P[u] là mảng đánh dấu các đỉnh <span id="MathJax-Element-168-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu đã được xử lí chưa. Ban đầu tất cả các giá trị đều là false.

Ta sẽ lặp <span id="MathJax-Element-169-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N">NN lần quá trình sau:

  • Tìm đỉnh <span id="MathJax-Element-170-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu có <span id="MathJax-Element-171-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D[u]">D[u]D[u] nhỏ nhất và <span id="MathJax-Element-172-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="P[u]=false">P[u]=falseP[u]=false.
  • Sau khi tìm được đỉnh <span id="MathJax-Element-173-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu, ta xét các đỉnh <span id="MathJax-Element-174-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="v">vv kề với đỉnh <span id="MathJax-Element-175-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu và tiến hành tối ưu hóa <span id="MathJax-Element-176-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D[v]">D[v]D[v]: nếu <span id="MathJax-Element-177-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D[v]&gt;D[u]+W[u,v]">D[v]>D[u]+W[u,v]D[v]>D[u]+W[u,v] thì <span id="MathJax-Element-178-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D[v]=D[u]+W[u,v]">D[v]=D[u]+W[u,v]D[v]=D[u]+W[u,v].
    • Nếu việc tối ưu hóa diễn ra, ta sẽ cập nhật <span id="MathJax-Element-179-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="trace[v]=u">trace[v]=utrace[v]=u.
  • Đánh dấu <span id="MathJax-Element-180-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="P[u]=true">P[u]=trueP[u]=true, nghĩa là đỉnh <span id="MathJax-Element-181-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu đã được xử lí xong

Độ phức tạp thuật toán: Ta có <span id="MathJax-Element-182-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N">NN lần lặp:

  • Bước đầu tiên có độ phức tạp <span id="MathJax-Element-183-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="O(N)">O(N)O(N) mỗi lần lặp.
  • Bước thứ hai có tổng độ phức tạp <span id="MathJax-Element-184-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="O(M)">O(M)O(M) qua tất cả các lần lặp

Như vậy độ phức tạp của cách cài đặt cơ bản sẽ là <span id="MathJax-Element-185-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="O(N2+M)">O(N2+M)O(N2+M).

Code:

const long long INF = 2000000000000000000LL;
struct Edge{
    int v;
    long long w;
};
void dijkstra(int n, int S, vector<vector<Edge>> E, vector<long long> &D, vector<int> &trace) {
    D.resize(n, INF);
    trace.resize(n, -1);
    
    vector<bool> P(n, 0);
    D[S] = 0;
    
    for (int i = 0; i < n; i++) {
        int uBest; // tìm đỉnh u chưa dùng, có khoảng cách nhỏ nhất
        long long Max = INF;
        for (int u = 0; u < n; u++) {
            if(D[u] < Max && P[u] == false) {
                uBest = u;
                Max = D[u];
            }
        }
        
        // cải tiến các đường đi qua u
        int u = uBest;
        P[u] = true;
        for(auto x : E[u]) {
            int v = x.v;
            long long w = x.w;
            if(D[v] > D[u] + w) {
                D[v] = D[u] + w;
                trace[v] = u;
            }
        }
    }
}

Cải tiến đối với đồ thị thưa

  • Nhận xét rằng bước đầu tiên: "Tìm đỉnh <span id="MathJax-Element-186-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu có <span id="MathJax-Element-187-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="Du">DuDu nhỏ nhất và <span id="MathJax-Element-188-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="Pu=false">Pu=falsePu=false", có thể được cải tiến. Ta có thể sử dụng cấu trúc dữ liệu Heap (cụ thể là Min Heap) hoặc cây nhị phân tìm kiếm để cải tiến bước này.
    • Mỗi lần tối ưu hóa <span id="MathJax-Element-189-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="Dv">DvDv, ta đẩy cặp <span id="MathJax-Element-190-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="Dv,v">Dv,vDv,v vào trong Heap.
    • Để tìm đỉnh có <span id="MathJax-Element-191-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="Du">DuDu nhỏ nhất, ta chỉ cần liên tục lấy phần tử trên cùng trong Heap ra, cho đến khi gặp đỉnh <span id="MathJax-Element-192-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu thỏa mãn <span id="MathJax-Element-193-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="Pu=false">Pu=falsePu=false.
  • Mỗi lần tối ưu <span id="MathJax-Element-194-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="Dv">DvDv, ta phải push vào Heap một lần. Với mỗi lần push vào trong Heap, ta đều phải pop ra lại một lần. Do có tối đa <span id="MathJax-Element-195-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="O(M)">O(M)O(M) lần tối ưu, độ phức tạp của thuật toán là <span id="MathJax-Element-196-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="O(MlogN)">O(MlogN)O(MlogN).

Độ phức tạp sau khi cải tiến: <span id="MathJax-Element-197-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="O(MlogN)">O(MlogN)O(MlogN)Lưu ý rằng với <span id="MathJax-Element-198-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="M">MM lớn thì độ phức tạp này không tốt hơn cài đặt cơ bản. Chứng minh như sau:

  • Ta có độ phức tạp của hai cách cài đặt:
    • Cách cài đặt cơ bản: <span id="MathJax-Element-199-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="O(N2+M)">O(N2+M)O(N2+M).
    • Cách cài đặt cải tiến: <span id="MathJax-Element-200-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="O(MlogN)">O(MlogN)O(MlogN).
  • Số lượng cạnh <span id="MathJax-Element-201-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="M">MM trong đơn đồ thị không vượt quá <span id="MathJax-Element-202-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N2">N2N2, như vậy độ phức tạp của cách cơ bản có thể được viết đơn giản thành <span id="MathJax-Element-203-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="O(N2)">O(N2)O(N2).
  • Để cách cài đặt cải tiến tốt hơn, ta cần <span id="MathJax-Element-204-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="MlogN&lt;N2">MlogN<N2MlogN<N2 suy ra <span id="MathJax-Element-205-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="M&lt;N2/logN">M<N2/logNM<N2/logN.
    • Ví dụ: đối với <span id="MathJax-Element-206-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N=105">N=105N=105, ta cần <span id="MathJax-Element-207-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="M&gt;6⋅108">M>6108M>6⋅108 để cách cài đặt cơ bản tốt hơn cách cài đặt cải tiến. Thực tế trong lập trình thi đấu khó có đồ thị nào có số cạnh lớn như vậy. Vì thế nhìn chung khi <span id="MathJax-Element-208-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N">NN lớn thì thuật <span id="MathJax-Element-209-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="O(MlogN)">O(MlogN)O(MlogN) luôn tốt hơn.

Code:

const long long INF = 2000000000000000000LL;
struct Edge{// kiểu dữ liệu tự tạo để lưu thông số của một cạnh.
    int v;
    long long w;
};
struct Node{// kiểu dữ liệu để lưu đỉnh u và độ dài của đường đi ngắn nhất từ s đến u.
    int u;
    long long Dist_u;
};
struct cmp{
    bool operator() (Node a, Node b) {
        return a.Dist_u > b.Dist_u;
    }
};
void dijkstraSparse(int n, int s, vector<vector<Edge>> &E, vector<long long> &D, vector<int> &trace) {
    D.resize(n, INF);
    trace.resize(n, -1);
    vector<bool> P(n, 0);
    
    D[s] = 0;
    priority_queue<Node, vector<Node>, cmp> h; // hàng đợi ưu tiên, sắp xếp theo dist[u] nhỏ nhất trước
    h.push({s, D[s]});
    
    while(!h.empty()) {
        Node x = h.top();
        h.pop();
        
        int u = x.u;
        if(P[u] == true) // Đỉnh u đã được chọn trước đó, bỏ qua
            continue;
            
        P[u] = true; // Đánh dấu đỉnh u đã được chọn
        for(auto e : E[u]) {
            int v = e.v;
            long long w = e.w; 
            
            if(D[v] > D[u] + w) {
                D[v] = D[u] + w;
                h.push({v, D[v]});
                trace[v] = u;
            }
        }
    }
}

Tìm lại đường đi ngắn nhất

Cũng giống như thuật toán Bellman-Ford, để tìm lại đường đi ngắn nhất từ <span id="MathJax-Element-210-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S">SS về <span id="MathJax-Element-211-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu, ta sẽ bắt đầu từ đỉnh <span id="MathJax-Element-212-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu, sau đó truy vết theo mảng <span id="MathJax-Element-213-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="trace">tracetrace ngược về <span id="MathJax-Element-214-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="S">SS.

vector<int> trace_path(vector<int> &trace, int S, int u) {
    if (u != S && trace[u] == -1) return vector<int>(0); // không có đường đi

    vector<int> path;
    while (u != -1) { // truy vết ngược từ u về S
        path.push_back(u);
        u = trace[u];
    }
    reverse(path.begin(), path.end()); // cần reverse vì đường đi lúc này là từ u về S
    
    return path;
}

3. Thuật toán Floyd-Warshall

Thuật toán Floyd-Warshll 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.

Bài toán

Cho đồ thị gồm <span id="MathJax-Element-215-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N">NN đỉnh và một ma trận trọng số <span id="MathJax-Element-216-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="W">WW, trong đó ô <span id="MathJax-Element-217-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="(i,j)">(i,j)(i,j) cho biết rằng có một đường đi trực tiếp từ <span id="MathJax-Element-218-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="i→j">iji→j với trọng số là <span id="MathJax-Element-219-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="Wi,j">Wi,jWi,j. Yêu cầu tìm đường đi ngắn nhất giữa mọi cặp đỉnh trên đồ thị.

Giới hạn bài toán: <span id="MathJax-Element-220-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="1≤N≤100">1N1001≤N≤100

Input: Dòng đầu tiên gồm số nguyên dương <span id="MathJax-Element-221-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N">NN, <span id="MathJax-Element-222-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N">NN dòng tiếp theo, mỗi dòng gồm <span id="MathJax-Element-223-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N">NN số biểu diễn một ma trận trong đó ô <span id="MathJax-Element-224-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="(i,j)">(i,j)(i,j) cho biết đường đi trực tiếp từ <span id="MathJax-Element-225-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="i→j">iji→j có trọng số là <span id="MathJax-Element-226-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="W[i,j]">W[i,j]W[i,j].

Output: Ma trận kết quả trong đó giá trị ô <span id="MathJax-Element-227-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="(i,j)">(i,j)(i,j) là đường đi ngắn nhất từ <span id="MathJax-Element-228-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="i→j">iji→j.

Sample Input

5
0 4 2 1 6
7 0 1 2 4
2 3 0 1 2
4 5 5 0 1
6 8 7 3 0

Sample Output

0 4 2 1 2
3 0 1 2 3
2 3 0 1 2
4 5 5 0 1
6 8 7 3 0

Ý tưởng của thuật toán.

Ý tưởng của thuật toán này là: "Liệu chúng ta có thể chèn một đỉnh <span id="MathJax-Element-229-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="k">kk vào đường đi ngắn nhất giữa 2 đỉnh <span id="MathJax-Element-230-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu và <span id="MathJax-Element-231-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="v">vv?".

  • Ví dụ như có một đường đi ngắn nhất từ <span id="MathJax-Element-232-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="0→4">040→4 như sau: <span id="MathJax-Element-233-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="0→1→2→3→4">012340→1→2→3→4. Vậy việc tính đường đi ngắn nhất từ <span id="MathJax-Element-234-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="0→4">040→4 hoàn toàn có thể được chia thành tính đường đi ngắn nhất từ <span id="MathJax-Element-235-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="0→2">020→2 sau đó cộng với đường đi ngắn nhất từ <span id="MathJax-Element-236-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="2→4">242→4. Tương tự thế đường đi ngắn nhất từ <span id="MathJax-Element-237-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="0→2">020→2 và <span id="MathJax-Element-238-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="2→4">242→4 lại tiếp tực được phân hoạch thành những đường đi ngắn nhất khác đơn giản hơn và tối ưu hơn.

Ta nhận thấy có một cấu trúc đệ quy, chia nhỏ bài toán ở đây. Ý tưởng này cho phép chúng ta thực hiện một thuật toán mang hương vị quy hoạch động như sau:

  • Gọi <span id="MathJax-Element-239-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D(u,v,k)">D(u,v,k)D(u,v,k) là đường đi ngắn nhất, trong đó ta chỉ được đi qua <span id="MathJax-Element-240-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="k">kk đỉnh đầu tiên (có số thứ tự từ <span id="MathJax-Element-241-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="0">00 đến <span id="MathJax-Element-242-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="k−1">k1k−1), ngoại trừ chính <span id="MathJax-Element-243-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu và <span id="MathJax-Element-244-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="v">vv. Ta có công thức truy hồi:
    • <span id="MathJax-Element-245-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D(u,v,0)=Wu,v">D(u,v,0)=Wu,vD(u,v,0)=Wu,v (không được dùng đỉnh nào ngoài chính <span id="MathJax-Element-246-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u,v">u,vu,v).
    • <span id="MathJax-Element-247-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D(u,u,k)=0">D(u,u,k)=0D(u,u,k)=0
    • <span id="MathJax-Element-248-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D(u,v,k)=">D(u,v,k)=D(u,v,k)= min của 2 trường hợp:
      • <span id="MathJax-Element-249-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D(u,v,k−1)">D(u,v,k1)D(u,v,k−1): ta không dùng đỉnh <span id="MathJax-Element-250-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="k">kk làm trung gian, giữ nguyên đường đi cũ.
      • <span id="MathJax-Element-251-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D(u,k,k−1)+D(k,v,k−1)">D(u,k,k1)+D(k,v,k1)D(u,k,k−1)+D(k,v,k−1): ta dùng đỉnh <span id="MathJax-Element-252-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="k">kk làm trung gian, từ đường đi <span id="MathJax-Element-253-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u→v">uvu→v thành đường đi <span id="MathJax-Element-254-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u→k→v">ukvu→k→v.

Đến đây ta có thể sử dụng trực tiếp công thức quy hoạch động để cài đặt thuật toán. Tuy nhiên, để đảm bảo bộ nhớ, ta có thể tính các <span id="MathJax-Element-255-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D(u,v,k)">D(u,v,k)D(u,v,k) với <span id="MathJax-Element-256-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="k">kk lần lượt từ <span id="MathJax-Element-257-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="1">11 đến <span id="MathJax-Element-258-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N">NN, và khi cài đặt chỉ cần lưu lại <span id="MathJax-Element-259-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D(u,v)">D(u,v)D(u,v).

Cài đặt

  • Định nghĩa:

    • <span id="MathJax-Element-260-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="W[u,v]">W[u,v]W[u,v] là giá trị đường đi trực tiếp từ <span id="MathJax-Element-261-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u→v">uvu→v.
    • <span id="MathJax-Element-262-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D[u,v]">D[u,v]D[u,v] là giá trị đường đi ngắn nhất từ <span id="MathJax-Element-263-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u→v">uvu→v.
    • <span id="MathJax-Element-264-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="trace[u,v]">trace[u,v]trace[u,v] là mảng truy vết đường đi ngắn nhất từ <span id="MathJax-Element-265-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u→v">uvu→v
  • Đồ thị sẽ được lưu dưới dạng ma trận kề. Ban đầu sẽ khởi tạo mọi <span id="MathJax-Element-266-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D[u,v]=W[u,v]">D[u,v]=W[u,v]D[u,v]=W[u,v] vì khi chưa tối ưu gì thì đường đi trực tiếp luôn là đường đi ngắn nhất.
    • <span id="MathJax-Element-267-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="trace[u,v]">trace[u,v]trace[u,v] sẽ khởi tạo bằng <span id="MathJax-Element-268-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu với mọi cặp <span id="MathJax-Element-269-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u,v">u,vu,v.
    • Nếu không có cạnh nối giữa <span id="MathJax-Element-270-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu và <span id="MathJax-Element-271-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="v">vv, coi như <span id="MathJax-Element-272-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="W[u,v]=∞">W[u,v]=W[u,v]=∞ .
  • Thuật toán chỉ cần một vòng lặp xét mọi đỉnh <span id="MathJax-Element-273-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="k">kk như một đỉnh trung gian. Tiếp theo đến là 2 vòng lặp <span id="MathJax-Element-274-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu, <span id="MathJax-Element-275-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="v">vv, có ý nghĩa thử chèn đỉnh <span id="MathJax-Element-276-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="k">kk vào giữa đường đi từ <span id="MathJax-Element-277-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu đến <span id="MathJax-Element-278-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="v">vv.
    • Nếu như <span id="MathJax-Element-279-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D[u,v]">D[u,v]D[u,v] được tối ưu bằng đỉnh <span id="MathJax-Element-280-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="k">kk, ta cập nhật thêm <span id="MathJax-Element-281-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="trace[u,v]=trace[k,v]">trace[u,v]=trace[k,v]trace[u,v]=trace[k,v]
  • Độ phức tạp của thuật toán là <span id="MathJax-Element-282-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="O(N3)">O(N3)O(N3).

Code: Thuật toán có thể được cài đặt rất dễ dàng chỉ với 3 vòng lặp:

void init_trace(vector<vector<int>> &trace) {
    int n = trace.size();
    for (int u = 0; u < n; u++) {
        for (int v = 0; v < n; v++) {
            trace[u][v] = u;
        }
    }
}

void floydWarshall(int n, vector<vector<long long>> &w, vector<vector<long long>> &D, vector<vector<int>> &trace) {
    D = w;
    init_trace(trace); // nếu cần dò đường đi
    
    for (int k = 0; k < n; k++) {
        for (int u = 0; u < n; u++) {
            for (int v = 0; v < n; v++) {
                if (D[u][v] > D[u][k] + D[k][v]) {
                    D[u][v] = D[u][k] + D[k][v];
                    trace[u][v] = trace[k][v];
                }
            }
        }
    }
}

Tìm lại đường đi ngắn nhất

Giống như hai thuật toán Bellman-Ford và Dijkstra, để tìm đường đi từ <span id="MathJax-Element-283-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu đến <span id="MathJax-Element-284-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="v">vv, ta sẽ bắt đầu từ <span id="MathJax-Element-285-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="v">vv, truy ngược về <span id="MathJax-Element-286-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u">uu theo mảng trace đã tìm được.

vector<int> trace_path(vector<vector<int>> &trace, int u, int v) {
    vector<int> path;
    while (v != u) { // truy vết ngược từ v về u
        path.push_back(v);
        v = trace[u][v];
    }
    path.push_back(u);
    
    reverse(path.begin(), path.end()); // cần reverse vì đường đi từ v ngược về u
    
    return path;
}

4. Lưu ý

  • Bảng so sánh các thuật toán được đề cập:
Bellman-Ford Dijkstra (cơ bản) Dijkstra (trên đồ thị thưa) Floyd-Warshall
Bài toán giải quyết Đường đi ngắn nhất một nguồn Đường đi ngắn nhất một nguồn Đường đi ngắn nhất một nguồn Đường đi ngắn nhất mọi cặp đỉnh
Độ phức tạp <span id="MathJax-Element-287-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="O(N∗M)">O(NM)O(N∗M) <span id="MathJax-Element-288-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="O(N2+M)">O(N2+M)O(N2+M) <span id="MathJax-Element-289-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="O(MlogN)">O(MlogN)O(MlogN) <span id="MathJax-Element-290-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="O(N3)">O(N3)O(N3)
Sử dụng được cho trọng số âm Không Không
Tìm được chu trình âm Không Không Không
  • Trong trường hợp có chu trình âm, thuật toán Floyd-Warshall có thể phải tính toán đến những giá trị rất nhỏ (về phía số âm), đủ để gây ra hiện tượng tràn số (thậm chí với <span id="MathJax-Element-291-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N">NN tương đối nhỏ). Cần phải chú ý đặc biệt đến trường hợp này khi cài đặt.
    • Một cách thường dùng để giải quyết trường hợp này là gán D[u][v] = max(D[u][v], -INF) ngay sau mỗi lần tối ưu, chặn không cho <span id="MathJax-Element-292-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="D[u,v]">D[u,v]D[u,v] xuống dưới hằng số âm vô tận.
  • Thuật toán Floyd-Warshall có thứ tự 3 vòng lặp là <span id="MathJax-Element-293-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="k→u→v">kuvk→u→v thay vì <span id="MathJax-Element-294-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="u→v→k">uvku→v→k (đỉnh trung gian phải được đặt ở vòng lặp ngoài cùng), đây là một nhầm lẫn tương đối phổ biến khi cài đặt.

  • Heap không phải là cấu trúc dữ liệu duy nhất có thể sử dụng khi cài đặt Dijkstra dành cho đồ thị thưa. Ta có thể sử dụng bất cứ cấu trúc dữ liệu nào hỗ trợ các thao tác "xóa khỏi tập hợp""cập nhật phần tử trong tập hợp""tìm phần tử nhỏ nhất trong tập hợp". Thực tế cây nhị phân tìm kiếm (std::set trong C++) cũng là một lựa chọn phổ biến khi cài đặt thuật toán này.

  • Với đồ thị thưa, không có trọng số âm, thay vì sử dụng thuật toán Floyd, ta có thể chạy thuật toán Dijkstra cải tiến <span id="MathJax-Element-295-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N">NN lần với <span id="MathJax-Element-296-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N">NN đỉnh nguồn để tìm đường đi ngắn nhất giữa mọi cặp đỉnh, với độ phức tạp tốt hơn thuật toán Floyd:
    • Ta có độ phức tạp của hai thuật toán:
      • Dijkstra cải tiến, <span id="MathJax-Element-297-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N">NN lần: <span id="MathJax-Element-298-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="O(N∗MlogN)">O(NMlogN)O(N∗MlogN)
      • Floyd-Warshall: <span id="MathJax-Element-299-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="O(N3)">O(N3)O(N3)
    • Như vậy, để Dijkstra <span id="MathJax-Element-300-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N">NN lần tốt hơn, ta cần có <span id="MathJax-Element-301-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="N∗MlogN&lt;N3">NMlogN<N3N∗MlogN<N3 suy ra <span id="MathJax-Element-302-Frame" class="MathJax" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 15px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;" tabindex="0" role="presentation" data-mathml="M&lt;N2/logN">M<N2/logNM<N2/logN (tương tự như so sánh giữa hai cách cài đặt thuật Dijkstra).

Bài tập vận dụng.

Thuật toán Bellman-Ford:

Thuật toán Dijkstra:

Thuật toán Floyd-Warshall: