Thuật toán Bellman-Ford cho đồ thị

Nắm vững thuật toán Dijkstra, phương pháp tham lam tìm đường đi ngắn nhất từ một đỉnh nguồn trên đồ thị có trọng số không âm. Đọc các cạnh có trọng số, xây dựng đầy đủ phép tính khoảng cách bằng ngôn ngữ bạn chọn, rồi trả lời các truy vấn về đường đi giữa hai đỉnh và đỉnh xa nhất.

Thuật toán đồ thị

Chứng nhận khi hoàn thành

• 9
• 4
• 1
• 54

Nắm vững thuật toán Prim để tìm cây khung nhỏ nhất: bắt đầu từ một đỉnh, mở rộng một cây bằng cách luôn thêm cạnh băng qua có trọng số nhỏ nhất. Xây dựng thuật toán bằng ngôn ngữ bạn chọn, rồi trả lời các truy vấn về cạnh nút thắt và tính liên thông, tương tự như thuật toán Kruskal.

Thuật toán đồ thị

Chứng nhận khi hoàn thành

• 9
• 4
• 1
• 55

Nắm vững thuật toán tìm kiếm theo chiều rộng, cách duyệt đồ thị theo từng lớp làm nền tảng cho việc tìm đường đi ngắn nhất. Xây dựng cách tra cứu các đỉnh kề, viết thuật toán BFS lặp với hàng đợi bằng ngôn ngữ bạn chọn, rồi dùng thuật toán đó để tìm khoảng cách đường đi ngắn nhất trong đồ thị không trọng số.

Thuật toán đồ thị

Chứng nhận khi hoàn thành

• 9
• 4
• 1
• 54

Nắm vững cách sắp xếp tô pô, tức là sắp xếp các đỉnh của đồ thị có hướng không chu trình sao cho mọi cạnh đều hướng về phía trước. Tính bậc vào, tạo thứ tự bằng thuật toán Kahn bằng ngôn ngữ bạn chọn, phát hiện chu trình và tìm đường đi dài nhất trong đồ thị có hướng không chu trình.

Thuật toán đồ thị

Chứng nhận khi hoàn thành

• 9
• 4
• 1
• 55

Nắm vững thuật toán Kruskal để tìm cây khung nhỏ nhất. Xây dựng cấu trúc union-find, tạo cây khung nhỏ nhất bằng cách thêm cạnh có trọng số thấp nhất mà không tạo chu trình, rồi trả lời các truy vấn về tính liên thông và cạnh thắt cổ chai.

Thuật toán đồ thị

Chứng nhận khi hoàn thành

• 9
• 4
• 1
• 57