! Dijkstra算法求两点间最短路径子程序
! 修改自 杨洪，图论常用算法选编，北京：中国铁道出版社，1988
! 陆新征，北京清华大学土木工程系
! 2007.1.12.

subroutine Dijkstra (N, NStart, NEnd, A, Dist, NNode, Path, Inf)
implicit none
integer,intent(in) :: N, NStart, NEnd ! 节点数目, 起点、终点节点号码
real*8,intent(in) :: A(N,N) ! 节点间有向距离矩阵
real*8,intent(out) :: Dist ! 最小距离
integer,intent(out) :: NNode, Path(N) ! 最小路径经过的节点数，最小路径节点数组
real*8 :: Inf ! 无穷大数

integer :: NodeMark(N) ! 节点是否已经标记
integer :: FormerNode(N) ! 由开始节点到第i节点最短通路的前一个顶点编号
real*8 :: S_to_i_Dist(N) ! 由开始节点到第i节点的最短通路长度
integer :: I,J,K, KK, G0
real*8 :: U, V, G

Dist=0.;
Path=0; NodeMark=0; FormerNode=NStart; S_to_i_Dist=Inf
NodeMark(NStart)=1; S_to_i_Dist(NStart)=0.d0; J=NStart

do
G=Inf; G0=0
do I=1,N
if(NodeMark(I).ne.0) cycle
U=S_to_i_Dist(I); V=S_to_i_Dist(J)+A(J,I)
S_to_i_Dist(I)=min(U,V)
if(U>V) FormerNode(I)=J
if(S_to_i_Dist(I)>=G.or.S_to_i_Dist(I)>=Inf) cycle
G0=I; G=S_to_i_Dist(I)
end do
if(G0==0) then
Dist=Inf
return
end if
NodeMark(G0)=1; J=G0
if(NodeMark(NEnd).ne.0) exit
end do
Dist=S_to_i_Dist(NEnd)
Path(1)=NEnd; J=NEnd; K=2
if(Dist==Inf) return
do
J=FormerNode(J)
Path(K)=J
K=K+1
if(J==NStart) exit
end do
NNode=K-1
do K=1, int(NNode/2)
I=Path(K)
J=NNode-K+1
Path(K)=Path(J)
Path(J)=I
end do
return
end subroutine