THUẬT TOÁN DIJKSTRA

      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


     


     Đề bài thuật toán:

   Bài : Cho đồ thị vô hướng và có trọng số G có n đỉnh, m cạnh. Hãy tìm đường đi ngắn             nhất từ đỉnh u đến đỉnh v của đồ thị theo thuật toán Dijkstra?

   Dữ liệu vào file 'Dijkstra.inp': dòng đầu là 4 số n, m, u, v; m dòng tiếp theo là danh sách         các cạnh cùng trọng số từng cạnh trong G.

   Kết quả ghi ra file 'Dijkstra.out': Nến có đường đi từ u đến v, dòng đầu ghi ra độ dài              đường     đi ngắn nhất từ u đến v; dòng thứ hai ghi các đỉnh nằm trên đường ngắn nhất từ u      đến v.

   Code Thuật toán Dijkstra.

   
     Các bạn có thể tham khảo lý thuyết đồ thị tại Lý thuyết đồ thị