Dijkstra最短路径算法的C语言实现

20114No．42011104JOURNALOFFUZHOUUNIVERSITYPhilosophyandSocialSciencesSerialNo．1042011－01－11。DijkstraC350108DijkstraC。、。Dijkstra。DijkstraCF259．22A1002－3321201104－0024－04、、。ShortestPathProblemSPP。。1。Dijkstra、、、1。Dijkstra。2ZWZW。DijkstraC。1Dijkstra112N2112N3、2N3、2N3、、D=VAaij=vivjωaij=ωijμstDμst=vi1vi2vi2vi3…vim－1vimμstvi1vimvi1vsvimvt。·42·μstμstWst=∑m－1t=1ωitit+1vsvtμ*vsvtWμ*=minμstWstωij≥0。、Dijkstra1．Dijkstravsvtμ*vs…vj…vk…vtvsμ*vjvkvsvjvk。μ*vsvtvsμ*μ*。vsvtvsvt。2．Dijkstra。vs。Ljdj。Ljvsvjdjvsvj。vsds=0vjj≠sLj=ωst。。1k=1d1s=0L1j=ωsjj≠s。N=vsN。2Lkjvxdkx=minjLkj3N=vs…vtdktvsvt⑸。4k=k+1vl∈NvxvLLkl=minLk－1ldk－1x+ωxl5vtvjdj+ωjt=dtvjvtvjvidi+ωij=djvivjvsvkvsvtμ*=vsvk…vivjvjvt、C1．10102102854000000783800000120000000000003000000011AF1A0F23ij40。。。2．dataij·52·10data0k0k2kdatakm0m3rn。datarndatarn≠0⑷datarn=0⑷4⑵datakmdatakm+1datakndatakn。⑸5⑴data0mdata0k+1data0ndata0n。⑹6。voidshortpathintkintijforj=0j＜NUMj++ifdatakj=0/**/ifj==NUM－1/**/acc++length_tempacc=length_tempacc－1+datakj/*、*/path_temp++bcc=j/**/iflength_tempacc＜length/**/length=length_tempaccfori=0i＜MAXi++pathi=path_tempilength_tempacc－－=0/*、*/length_tempacc－－=0path_tempbcc－－=0path_tempbcc－－=0elseacc++length_tempacc=length_tempacc－1+datakj/*、*/path_temp++bcc=j/**/shortpathj/**/·62·elseifdatakj==0＆＆j==NUM－1length_tempacc－－=0/*、*/path_tempbcc－－=0、。ZW。。07、、、、、1、2、3、4、5、6。km22TURBOC4750—1—5—7———。。8725165572．4512MXP1。Dijkstra、。1《》1994。2E．《》1984。、、《》《》19994。、《》《》20031。、、《DijkstraDijkstraN》《》20069。、《》《》20093。·72·