C++求最短路径的两种实现方法示例代码是小编为大家整理的一个C++求最短路径例子,本实例向大家演示了标号法求解单源点最短路径、Floyed算法求解所有顶点对之间的最短路径、Dijkstra 算法求最短路径,,赶紧来详细了解一下吧:
1、标号法求解单源点最短路径:
var a:array[1..maxn,1..maxn] of integer; b:array[1..maxn] of integer; {b[i]指顶点i到源点的最短路径} mark:array[1..maxn] of boolean; procedure bhf; var best,best_j:integer; begin fillchar(mark,sizeof(mark),false); mark[1]:=true; b[1]:=0;{1为源点} repeat best:=0; for i:=1 to n do If mark[i] then {对每一个已计算出最短路径的点} for j:=1 to n do if (not mark[j]) and (a[i,j]>0) then if (best=0) or (b[i]+a[i,j]<best) then begin best:=b[i]+a[i,j]; best_j:=j; end; if best>0 then begin b[best_j]:=best;mark[best_j]:=true; end; until best=0; end;{bhf}
2、Floyed算法求解所有顶点对之间的最短路径:
procedure floyed; begin for I:=1 to n do for j:=1 to n do if a[I,j]>0 then p[I,j]:=I else p[I,j]:=0; {p[I,j]表示I到j的最短路径上j的前驱结点} for k:=1 to n do {枚举中间结点} for i:=1 to n do for j:=1 to n do if a[i,k]+a[j,k]<a[i,j] then begin a[i,j]:=a[i,k]+a[k,j]; p[I,j]:=p[k,j]; end; end;
3、Dijkstra 算法:
var a:array[1..maxn,1..maxn] of integer; b,pre:array[1..maxn] of integer; {pre[i]指最短路径上I的前驱结点} mark:array[1..maxn] of boolean; procedure dijkstra(v0:integer); begin fillchar(mark,sizeof(mark),false); for i:=1 to n do begin d[i]:=a[v0,i]; if d[i]<>0 then pre[i]:=v0 else pre[i]:=0; end; mark[v0]:=true; repeat {每循环一次加入一个离1集合最近的结点并调整其他结点的参数} min:=maxint; u:=0; {u记录离1集合最近的结点} for i:=1 to n do if (not mark[i]) and (d[i]<min) then begin u:=i; min:=d[i]; end; if u<>0 then begin mark[u]:=true; for i:=1 to n do if (not mark[i]) and (a[u,i]+d[u]<d[i]) then begin d[i]:=a[u,i]+d[u]; pre[i]:=u; end; end; until u=0; end;
这几种求最短路径的算法可以适用不同的条件下,大家可以有针对性的选择使用。