怎样用动态规划法求单源最短路径?书上倒是有dijkstra方法,可是老师要求用动态规范法.,
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/06 16:40:24
![怎样用动态规划法求单源最短路径?书上倒是有dijkstra方法,可是老师要求用动态规范法.,](/uploads/image/z/13544549-53-9.jpg?t=%E6%80%8E%E6%A0%B7%E7%94%A8%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%B3%95%E6%B1%82%E5%8D%95%E6%BA%90%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84%3F%E4%B9%A6%E4%B8%8A%E5%80%92%E6%98%AF%E6%9C%89dijkstra%E6%96%B9%E6%B3%95%2C%E5%8F%AF%E6%98%AF%E8%80%81%E5%B8%88%E8%A6%81%E6%B1%82%E7%94%A8%E5%8A%A8%E6%80%81%E8%A7%84%E8%8C%83%E6%B3%95.%2C)
怎样用动态规划法求单源最短路径?书上倒是有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;
动态规划的方法,貌似没听说过.
或许是我孤陋寡闻了...