Triển khai (phần 2)
Bài học 6 trên 9 trong khóa học Thuật toán Dijkstra, thuật toán đồ thị của Coddy.
Bây giờ là phép tính đường đi ngắn nhất theo cách tham lam.
Thử thách
Trung bìnhBây giờ, hãy xây dựng thuật toán hoàn chỉnh.
Viết một hàm có tên dijkstra nhận n, mảng phẳng edges (các bộ ba, có hướng, trọng số không âm) và source, rồi trả về một mảng trong đó vị trí v là khoảng cách ngắn nhất từ source đến v. Dùng -1 cho các đỉnh không thể đến được.
Đặt tất cả khoảng cách bằng một giá trị "infinity" lớn, ngoại trừ khoảng cách đến đỉnh nguồn là 0. Sau đó, lặp lại n lần: xác định đỉnh chưa được thăm gần nhất và nới lỏng các cạnh đi ra từ đỉnh đó.
Tự làm thử
#include <stdlib.h>
int* dijkstra(int n, int* edges, int edges_size, int source, int* returnSize) {
// Viết code tại đây
*returnSize = 0;
return edges;
}
Tự kiểm traBài học này có một bài trắc nghiệm ngắn. Bắt đầu bài học để trả lời và theo dõi tiến độ.
Tất cả bài học trong Thuật toán Dijkstra, thuật toán đồ thị
2Thuật toán
Cách hoạt động?Mã giảTriển khai (phần 1)Triển khai (phần 2)
Độ phức tạp thời gian và không gianTự luyện tập: Trình biên dịch C online