Code666 (代码贴、代码片段)

[Delphi (Object Pascal)] pascal经典算法 - Dijkstra 算法求最短路径 →→→→→进入此内容的聊天室

来自 , 2019-07-11, 写在 Delphi (Object Pascal), 查看 109 次.
URL http://www.code666.cn/view/a76c0abe
  1. var
  2.   a: array[1..maxn, 1..maxn] of Integer;
  3.   b, pre: array[1..maxn] of Integer; {pre[i]指最短路径上I的前驱结点}
  4.   mark: array[1..maxn] of Boolean;
  5.  
  6. procedure dijkstra(v0: Integer);
  7. begin
  8.   FillChar(mark, SizeOf(mark), false);
  9.   for i := 1 to n do
  10.   begin
  11.     d[i] := a[v0, i];
  12.     if d[i] <> 0 then
  13.       pre[i] := v0
  14.     else
  15.       pre[i] := 0;
  16.   end;
  17.   mark[v0] := true;
  18.   repeat {每循环一次加入一个离1集合最近的结点并调整其他结点的参数}
  19.     Min := MaxInt;
  20.     u   := 0; {u记录离1集合最近的结点}
  21.     for i := 1 to n do
  22.       if (not mark[i]) and (d[i] < Min) then
  23.       begin
  24.         u := i;
  25.         Min := d[i];
  26.       end;
  27.     if u <> 0 then
  28.     begin
  29.       mark[u] := true;
  30.       for i := 1 to n do
  31.         if (not mark[i]) and (a[u, i] + d[u] < d[i]) then
  32.         begin
  33.           d[i] := a[u, i] + d[u];
  34.           pre[i] := u;
  35.         end;
  36.     end;
  37.   until u = 0;
  38. end;
  39. //delphi/6608

回复 "pascal经典算法 - Dijkstra 算法求最短路径"

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666