Tìm kiếm đường đi ngắn nhất trong đồ thị với Pascal

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;

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.