[Thuật toán] Prim - Tìm cây khung nhỏ nhất

 Thuật toán Kruskal làm việc kém hiệu quả đối với những đồ thị có số cạnh khoảng m=n (n-1)/2. Trong những tình huống như vậy, thuật toán Prim tỏ ra hiệu quả hơn. Thuật toán Prim còn được mang tên là người láng giềng gần nhất. Trong thuật toán này, bắt đầu tại một đỉnh tuỳ...

[Thuật toán] Tìm cây khung nhỏ nhất

Bài toán cây khung nhỏ nhất của đồ thị là một trong số những bài toán tối ưu trên đồ thị được ứng dụng trong nhiều lĩnh vực khác nhau của đời sống. Trong mục này chúng ta sẽ trình bày những thuật toán cơ bản để giải bài toán này. Trước hết chúng ta phát biểu nội dung của bài toán.     ...

[Thuật toán] Tìm đường đi ngắn nhất Floyd

 Xét đồ thị G =<V, E>: trong đó |V| = n, |E| = m. Với mỗi cạnh (u, v)∈E, ta đặt tương ứng với nó một số thực A<u,v> được gọi là trọng số của cạnh. Ta sẽ đặt A[u,v]=∞ nếu (u, v)∉E. Nếu dãy v0, v1,..., vk là một đường đi trên G thì tổng của tất cả các cạnh...

[Thuật toán] Tìm đường đi ngắn nhất Dijkstra

 Xét đồ thị G =<V, E>: trong đó |V| = n, |E| = m. Với mỗi cạnh (u, v)∈E, ta đặt tương ứng với nó một số thực A<u,v> được gọi là trọng số của cạnh. Ta sẽ đặt A[u,v]=∞ nếu (u, v)∉E. Nếu dãy v0, v1,..., vk là một đường đi trên G thì tổng...

[Thuật toán] Prim - Tìm cây khung nhỏ nhất

 Thuật toán Kruskal làm việc kém hiệu quả đối với những đồ thị có số cạnh khoảng m=n (n-1)/2. Trong những tình huống như vậy, thuật toán Prim tỏ ra hiệu quả hơn. Thuật toán Prim còn được mang tên là người láng giềng gần nhất. Trong thuật toán này, bắt đầu tại một đỉnh tuỳ...

[Thuật toán] Kruskal - Tìm cây khung nhỏ nhất

Xem thuật toán Prim - tìm cây khung nhỏ nhất tại đây. Thuật toán sẽ xây dựng tập cạnh T của cây khung nhỏ nhất H=<V, T> theo từng bước như sau: 1.  Sắp xếp các cạnh của đồ thị G theo thứ tự tăng dần của trọng số cạnh; 2.  Xuất phát từ tập cạnh T=φ, ở...