作业帮怎样用动态规划法求单源最短路径?书上倒是有dijkstra方法,可是老师要求用动态规范法.,
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/01 23:14:49
怎样用动态规划法求单源最短路径?书上倒是有dijkstra方法,可是老师要求用动态规范法.,
怎样用动态规划法求单源最短路径?
书上倒是有dijkstra方法,可是老师要求用动态规范法.,
怎样用动态规划法求单源最短路径?书上倒是有dijkstra方法,可是老师要求用动态规范法.,
话说可以用spfa或者说dijkstra.这两种主要是广度优先搜索的思想.时间复杂度分别是
O(n^2)和O(nlogn)的.这两种是比较常见的求单元最短路径.
dijkstra算法比较好写,但时间复杂度相对较高.
Procedure dijk(start:longint);
Var
b:array[-10..120] of boolean;
next:longint;
min:longint;
i,j:longint;
Begin
fillchar(b,sizeof(b),false);
d[start,start]:=0;
for i:=1 to n do begin
min:=1000000;
for j:=1 to n do begin
if (not b[j]) and (d[start,j]-1) and (min>d[start,j]) then
begin
min:=d[start,j];
next:=j;
end;
end;
if min1000000 then begin
b[next]:=true;
for j:=1 to n do
if (map[next,j]-1) and ( (d[start,j]>map[next,j]+d[start,next]) or (d[start,j]=-1) ) then begin
d[start,j]:=d[start,next]+map[next,j];
end;
end;
end;//for i
End;
动态规划的方法,貌似没听说过.
或许是我孤陋寡闻了...