Bài toán tìm đường đi ngắn nhất trong pascal năm 2024

Question

Để tìm đường đi ngắn nhất trong đồ thị bằng Pascal, ta có thể sử dụng thuật toán Dijkstra hoặc thuật toán Bellman-Ford.

Đầu tiên, ta cần tạo một ma trận trọng số để lưu trữ khoảng cách giữa các đỉnh trong đồ thị. Nếu có một cạnh nối giữa hai đỉnh u và v, với trọng số w, ta sẽ lưu trữ giá trị w tại vị trí (u, v) và (v, u) trong ma trận.

Sau đó, ta chọn một đỉnh bất kỳ làm điểm bắt đầu, và tính toán khoảng cách ngắn nhất từ điểm bắt đầu đến các đỉnh khác trong đồ thị bằng thuật toán Dijkstra hoặc Bellman-Ford.

Dưới đây là mã Pascal cho thuật toán Dijkstra:

type TNode = record

ID: Integer;
Dist: Integer;

end; var N: Integer; // số đỉnh trong đồ thị W: array of array of Integer; // ma trận trọng số D: array of Integer; // khoảng cách ngắn nhất từ điểm bắt đầu đến các đỉnh khác Q: array of TNode; // hàng đợi đỉnh cần xử lý Visited: array of Boolean; // đánh dấu đỉnh đã xét procedure Dijkstra(S: Integer); var i, j, u, v, dist: Integer; begin SetLength(D, N); SetLength(Q, N); SetLength(Visited, N); for i := 0 to N - 1 do begin

D[i] := MaxInt; // khởi tạo khoảng cách ban đầu là vô cực
Visited[i] := False; // đánh dấu chưa xét đỉnh i

end; D[S] := 0; // khoảng cách từ điểm bắt đầu đến chính nó bằng 0 Q[0].ID := S; Q[0].Dist := 0; for i := 1 to N - 1 do begin

// chọn đỉnh u có khoảng cách ngắn nhất từ điểm bắt đầu đến u
u := -1;
for j := 0 to N - 1 do
  if (not Visited[j]) and ((u = -1) or (D[j] < D[u])) then
    u := j;
if D[u] = MaxInt then
  Break; // không còn đỉnh nào có thể xét được
Visited[u] := True; // đánh dấu đỉnh u đã xét
// cập nhật khoảng cách từ điểm bắt đầu đến các đỉnh kề với u
for v := 0 to N - 1 do
begin

// nếu có cạnh nối giữa u và v if W[u, v] <> 0 then begin dist := D[u] + W[u, v]; if dist < D[v] then begin

D[v] := dist; // cập nhật khoảng cách ngắn nhất từ điểm bắt đầu đến v
Q[i].ID := v;
Q[i].Dist := dist;

end; end;

Trong đoạn mã trên, biến S là đỉnh bắt đầu của đường đi ngắn nhất, N là số đỉnh trong đồ thị, W là ma trận trọng số, D là mảng lưu trữ khoảng cách ngắn nhất từ điểm bắt đầu đến các đỉnh khác, Q là hàng đợi đỉnh cần xử lý, Visited là mảng đánh dấu các đỉnh đã xét.

Sau khi chạy hàm Dijkstra với đỉnh bắt đầu là S, ta sẽ có được mảng D chứa khoảng cách ngắn nhất từ điểm bắt đầu đến các đỉnh khác trong đồ thị. Ta có thể in ra kết quả này bằng cách duyệt qua mảng D và in ra các giá trị tương ứng với các đỉnh trong đồ thị.

Chú ý rằng đoạn mã trên chỉ áp dụng cho đồ thị không có cạnh có trọng số âm. Nếu đồ thị có cạnh có trọng số âm, ta cần sử dụng thuật toán Bellman-Ford để tìm đường đi ngắn nhất.

Dưới đây là một ví dụ về cách cài đặt thuật toán Dijkstra bằng ngôn ngữ Pascal:

program ShortestPath; const MAXN = 1000; INF = 1000000000; type TEdge = record

v, w: LongInt;

end; var S, N, M, u, v, w, i, j, minDist, minNode: LongInt; W: array[1..MAXN, 1..MAXN] of LongInt; // ma trận trọng số D: array[1..MAXN] of LongInt; // mảng khoảng cách ngắn nhất Q: array[1..MAXN] of TEdge; // hàng đợi đỉnh cần xử lý Visited: array[1..MAXN] of Boolean; // mảng đánh dấu đỉnh đã xét begin // Nhập vào số đỉnh N, số cạnh M và đỉnh bắt đầu S Readln(N, M, S); // Khởi tạo ma trận trọng số for i := 1 to N do

for j := 1 to N do
  W[i, j] := 0;

// Nhập vào các cạnh và trọng số tương ứng for i := 1 to M do begin

Readln(u, v, w);
W[u, v] := w;

end; // Khởi tạo mảng khoảng cách ngắn nhất và hàng đợi for i := 1 to N do begin

D[i] := INF;
Q[i].v := i;
Q[i].w := INF;

end; // Điểm bắt đầu có khoảng cách ngắn nhất bằng 0 D[S] := 0; Q[S].w := 0; // Xử lý hàng đợi cho đến khi nó rỗng while True do begin

// Tìm đỉnh có khoảng cách ngắn nhất trong hàng đợi
minDist := INF;
minNode := -1;
for i := 1 to N do
  if not Visited[i] and (Q[i].w < minDist) then
  begin
    minDist := Q[i].w;
    minNode := i;
  end;
// Nếu không tìm thấy đỉnh có khoảng cách ngắn nhất thì dừng vòng lặp
if minNode = -1 then
  Break;
// Đánh dấu đỉnh đã xét
Visited[minNode] := True;
// Xét các đỉnh kề với đỉnh hiện tại và cập nhật khoảng cách ngắn nhất
for i := 1 to N do
begin
  if W[minNode, i] <> 0 then
  begin
    if D[minNode] + W[minNode, i] < D[i] then
    begin
      D[i] := D[minNode] + W[minNode, i];
  Q[i].w := D[i];
end;

end; end; // In ra khoảng cách ngắn nhất từ đỉnh bắt đầu đến các đỉnh còn lại for i := 1 to N do begin if D[i] = INF then Writeln('Khong co duong di tu ', S, ' den ', i) else Writeln('Khoang cach ngan nhat tu ', S, ' den ', i, ': ', D[i]); end; end.

Đây là một chương trình Pascal cài đặt thuật toán Dijkstra. Chương trình này nhận đầu vào là số đỉnh N, số cạnh M và đỉnh bắt đầu S, sau đó nhập vào danh sách các cạnh và trọng số tương ứng. Cuối cùng, chương trình sử dụng thuật toán Dijkstra để tìm đường đi ngắn nhất từ đỉnh bắt đầu đến các đỉnh còn lại trong đồ thị, và in ra kết quả.

mẹo hay