Lý thuyết đồ thị for i := 1 to n do begin d[i] := c[S, i]; Trace[i] := S; end; FillChar(Free, SizeOf(Free), True); end; procedure Dijkstra; var i, u, v: Integer; min: Integer; begin repeat {Thuật toán Dijkstra} | Lý thuyết đồ thị 62 for i 1 to n do begin d i c S i Trace i S end FillChar Free SizeOf Free True end procedure Dijkstra Thuật toán Dijkstra var i u v Integer min Integer begin repeat Tìm trong các đỉnh có nhãn tự do ra đỉnh u có d u nhỏ nhất u 0 min maxC for i 1 to n do if Free i and d i min then begin min d i u i end Thuật toán sẽ kết thúc khi các đỉnh tự do đều có nhãn x hoặc đã chọn đến đỉnh F if u 0 or u F then Break Cố định nhãn đỉnh u Free u False Dùng đỉnh u tối ưu nhãn những đỉnh tự do kề với u for v 1 to n do if Free v and d v d u c u v then begin d v d u c u v Trace v u end until False end procedure PrintResult In đường đi từ S tới F begin if d F maxC then WriteLn Path from S to F not found else begin WriteLn Distance from S to F d F while F S do begin Write F - F Trace F end WriteLn S end end begin Assign Input Reset Input Assign Output Rewrite Output LoadGraph Init Dijkstra PrintResult Close Input Close Output end. Lê Minh Hoàng Lý thuyết đồ thị 63 V. THUẬT TOÁN DIJKSTRA VÀ CẤU TRÚC HEAP Nếu đồ thị có nhiều đỉnh ít cạnh ta có thể sử dụng danh sách kề kèm trọng số để biểu diễn đồ thị tuy nhiên tốc độ của thuật toán DIJKSTRA vẫn khá chậm vì trong trường hợp xấu nhất nó cần n lần cố định nhãn và mỗi lần tìm đỉnh để cố định nhãn sẽ mất một đoạn chương trình với độ phức tạp O n . Để tăng tốc độ người ta thường sử dụng cấu trúc dữ liệu Heap để lưu các đỉnh chưa cố định nhãn. Heap ở đây là một cây nhị phân hoàn chỉnh thoả mãn Nếu u là đỉnh lưu ở nút cha và v là đỉnh lưu ở nút con thì d u d v . Đỉnh r lưu ở gốc Heap là đỉnh có d r nhỏ nhất . Tại mỗi bước lặp của thuật toán Dijkstra có hai thao tác Tìm đỉnh cố định nhãn và Sửa nhãn. Thao tác tìm đỉnh cố định nhãn sẽ lấy đỉnh lưu ở gốc Heap cố định nhãn đưa phần tử cuối Heap vào thế chỗ và thực hiện việc vun đống Adjust Thao tác sửa nhãn sẽ duyệt danh sách kề của đỉnh vừa cố định nhãn và sửa nhãn những đỉnh tự do kề với đỉnh này mỗi lần sửa nhãn một đỉnh nào đó ta xác định đỉnh này nằm ở .
