📄 graph_short_path_dijk.htm
字号:
<html><title>Dijkstra算法求两点间最短路径子程序</title><body bgcolor="#FFFFFF"><STYLE media=screen type=text/css> #floater { POSITION: absolute; VISIBILITY: visible; WIDTH: 10px; Z-INDEX: 10 } </STYLE> <IFRAME marginWidth=0 marginHeight=0 src="../commontop.html" frameBorder=0 width="881" height="135" scrolling=no topmargin="0"> </IFRAME> <br><p>! Dijkstra算法求两点间最短路径子程序<br> ! 修改自 杨洪，图论常用算法选编，北京：中国铁道出版社，1988<br> ! 陆新征，北京清华大学土木工程系<br> ! 2007.1.12.</p><IFRAME marginWidth=0 marginHeight=0 src="../keywords/cndown.html" frameBorder=0 width="881" height="140" scrolling=no topmargin="0"> </IFRAME><p>subroutine Dijkstra (N, NStart, NEnd, A, Dist, NNode, Path, Inf)<br> implicit none<br> integer,intent(in) :: N, NStart, NEnd ! 节点数目, 起点、终点节点号码<br> real*8,intent(in) :: A(N,N) ! 节点间有向距离矩阵<br> real*8,intent(out) :: Dist ! 最小距离<br> integer,intent(out) :: NNode, Path(N) ! 最小路径经过的节点数，最小路径节点数组<br> real*8 :: Inf ! 无穷大数</p><p> integer :: NodeMark(N) ! 节点是否已经标记<br> integer :: FormerNode(N) ! 由开始节点到第i节点最短通路的前一个顶点编号<br> real*8 :: S_to_i_Dist(N) ! 由开始节点到第i节点的最短通路长度<br> integer :: I,J,K, KK, G0<br> real*8 :: U, V, G</p><p> Dist=0.; <br> Path=0; NodeMark=0; FormerNode=NStart; S_to_i_Dist=Inf<br> NodeMark(NStart)=1; S_to_i_Dist(NStart)=0.d0; J=NStart</p><p> do <br> G=Inf; G0=0<br> do I=1,N<br> if(NodeMark(I).ne.0) cycle<br> U=S_to_i_Dist(I); V=S_to_i_Dist(J)+A(J,I)<br> S_to_i_Dist(I)=min(U,V)<br> if(U>V) FormerNode(I)=J<br> if(S_to_i_Dist(I)>=G.or.S_to_i_Dist(I)>=Inf) cycle<br> G0=I; G=S_to_i_Dist(I)<br> end do<br> if(G0==0) then<br> Dist=Inf<br> return<br> end if<br> NodeMark(G0)=1; J=G0<br> if(NodeMark(NEnd).ne.0) exit<br> end do<br> Dist=S_to_i_Dist(NEnd)<br> Path(1)=NEnd; J=NEnd; K=2<br> if(Dist==Inf) return<br> do<br> J=FormerNode(J)<br> Path(K)=J<br> K=K+1<br> if(J==NStart) exit<br> end do<br> NNode=K-1<br> do K=1, int(NNode/2)<br> I=Path(K)<br> J=NNode-K+1<br> Path(K)=Path(J)<br> Path(J)=I<br> end do<br> return<br> end subroutine </p><p><br> <br></p><table width="881" border="0"> <tr> <td width="115"> <div align="center"><font size="2"><a href="../gbindex.htm">个人信息</a></font></div> </td> <td width="115"> <div align="center"><font size="2"><a href="../research.htm">研究工作</a></font></div> </td> <td width="115"> <div align="center"><font size="2"><a href="../pratical.htm">实际工程</a></font></div> </td> <td width="115"> <div align="center"><font size="2"><a href="../publications.htm">论文工作</a></font></div> </td> <td width="115"> <div align="center"><font size="2"><a href="../download.htm">资料下载</a></font></div> </td> <td width="115"> <div align="center"><font size="2"><a href="../issues.htm">专题</a></font></div> </td> <td width="115"> <div align="center"><font size="2"><a href="../others.htm">其他</a></font></div> </td> </tr></table><p> </p><div id="floater" style="position:absolute; left:900px; top:160px; width:121px; height:600px; z-index:12"> <IFRAME marginWidth=0 marginHeight=0 src="../cnNews.htm" frameBorder=0 width="120" height="470" scrolling=no topmargin="0"> </IFRAME> <p></p><div align="left"><font size="2" color="#0000FF"><a href="http://www.thu-civil.net/" target="_parent"><b>我们的实验室</b></a></font></div></div> <SCRIPT language=JavaScript src="../java/floater.js"> </SCRIPT> <IFRAME marginWidth=0 marginHeight=0 src="../horiz.htm" frameBorder=0 width="612" height="300" scrolling=no topmargin="0"> </IFRAME> <script src="http://www.thu-concrete.net/luxz/count.asp?style=0"></script><script src="http://www.google-analytics.com/urchin.js" type="text/javascript"></script><script type="text/javascript">_uacct = "UA-257704-1";urchinTracker();</script></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -