图算法（二）单源最短路径Single-SourceShortestPath(Dijkstra算法)负权边的有向图单源最短有路径Bellman-Ford算法单源最短路径Single-SourceShortestPath权非负的单源最短路径算法（Dijkstra）v5权非负的单源最短路径算法（Dijkstra）权非负的单源最短路径算法（Dijkstra）权非负的单源最短路径算法（Dijkstra）DijkstraDijkstraDijkstra权非负的单源最短路径算法（Dijkstra）v6v1到其它各点的最短路DistDijkstra算法：1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。权非负的单源最短路径算法（Dijkstra）权非负的单源最短路径算法（Dijkstra）DijkstraDijkstraDijkstraConstmaxvalue=99999.0maxlength=100;TypeArr1=array[1..maxlength]ofinteger;Arr2=array[1..maxlength,1..maxlength]ofreal;Arr3=array[1..maxlength]ofreal;Varprev:Arr1;c:Arr2;dist:Arr3;s:array[1..maxlength]ofbooleann:integer;Procedureshortpaths(n,v:integer);{单源最短路径问题的Digkstra算法}Vari,j,u:integer;temp,newdist:real;beginfori:=1tondobegindist[i]:=c[v,i];s[i]:=false;if(dist[i]=maxvalue)thenprev[i]:=0elseprev[i]:=v;end;Dist[v]:=0;s[v]:=true;Fori:=1ton-1dobegintemp:=maxvalue;u:=v;forj:=1tondoif((nots[j])and(dist[j]<temp))thenbeginu:=j;temp:=dist[j];end;s[u]:=true;Forj:=1tondoif((nots[j])and(c[u,j]<maxvalue))thenbeginnewdist:=dist[u]+c[u,j];if(newdist<dist[j])thenbegindist[j]:=newdist;prev[j]:=u;endendendend;Procedureshortpaths(n,v:integer);{单源最短路径问题的Digkstra算法}Vari,j,u:integer;temp,newdist:real;beginfori:=1tondobegindist[i]:=c[v,i];s[i]:=false;if(dist[i]=maxvalue)thenprev[i]:=0elseprev[i]:=v;end;Dist[v]:=0;s[v]:=true;Fori:=1ton-1dobegintemp:=maxvalue;u:=v;forj:=1tondoif((nots[j])and(dist[j]<temp))thenbeginu:=j;temp:=dist[j];end;s[u]:=true;Forj:=1tondoif((nots[j])and(c[u,j]<maxvalue))thenbeginnewdist:=dist[u]+c[u,j];if(newdist<dist[j])thenbegindist[j]:=newdist;prev[j]:=u;endendendend;Dijkstra青蛙跳青蛙跳解题思路：普通最短路径（Dij算法）：路径长度（边权之和）最小路径长度本题：路径“长度”（各边的最大权，最远两块石头的距离，越远越青蛙越难跨越）最大路径权（路径“长度”越大青蛙越难跨越，因此青蛙要选择路径“长度”最小的路即路中需跳跃的最远距离要最小）有向无环图（DAG）最短路径1Dag的单源最短路径问题具有最优子结构性质,与Dijkstra类似可以用贪心算法求解.Functionshortpath(s:integer):boolean;p142varI,j,k:integer;p:wpointer;Beginifnottopsortthenbeginshortpath:=false;exit;end;Reverse;Shortp