Thuật toán Pascal cơ bản

Tiếp tục với chủ đề đồ thị, hai thuật toán Prim và kruskal đều tìm cây khung cực tiểu nhỏ nhất. Hai thuật toán trên được viết bằng ngôn ngữ Pascal, với kết quả ra file "prim.out" hay "kruskal.out", file dữ liệu ma trận kề là "prim.inp" hay "kruskal.inp" Đề bài thuật toán: Bài: Cho đồ thị vô hướng, có trọng số G gồm n đỉnh, m cạnh. Hãy tìm cây khung cực tiểu của đồ thị G theo thuật toán Prim? Dữ liệu vào file 'Prim.inp': Dòng đầu là 2 số n, m; m dòng tiếp theo là m bộ 3 số i, j, k mỗi số cách nhau một dấu cách, thể hiện 2 đỉnh i, j có cạnh nối với nhau có độ dài là k. Kết quả ghi ra file 'Prim.out': Dòng đầu là tổng độ dài của cây khung cực tiểu; các dòng tiếp theo là danh sách các cạnh được chọn trong cây khung. Bài: Cho đồ thị vô hướng, có trọng số G gồm n đỉnh, m cạnh. Hãy tìm cây khung cực tiểu của đồ thị G theo thuật toán Kruskal? Dữ liệu vào file 'Kruskal.inp' dòng đầu là 2 số n, m; m dòng tiếp theo là m bộ 3...

      Hôm nay, chúng tôi sẽ cung cấp cho các bạn thuật toán Dijkstra trên đồ thị viết bằng ngôn ngữ Pascal. Ở đây kết quả được đưa ra file "Dijkstra.out" và dữ liệu vào file "Dijkstra.inp" dưới dạng ma trận kề.           Thuật toán Dijkstra sẽ giúp tìm đường đi ngắn nhất từ đỉnh u (đỉnh nguồn) đến mọi đỉnh còn lại của đồ thị trên đô thị có trọng số.       Ý tưởng thuật toán: Tìm một đỉnh k  có đường đi ngắn nhất đến u. Sau đó xét xem giữa đỉnh u và i bất kỳ ( đỉnh đích). Sau đó nếu D[i] > D[k] + A[k, i] thì gán D[i] cho D[k] + A[k, i]. Trong này D[i] là chi phí từ u đến i, D[k] là chi phí từ u đến k, A[k, i] là chi phí từ k đến i. Hiểu nôm na là xen đỉnh k vào quãng đường từ u đến i.           Thuật toán Dijkstra là dạng thuật toán quy hoạch động, với độ phức tạp thông thường là n bình phương.           Mô tả thuật toán Dijkstra         ...