https://www.jb51.cc/csharp/1193261.html

编程之家收集整理的这篇文章主要介绍了用C++实现最短路径之Dijkstra算法，编程之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。

网络层的链路状态路由选择算法（LS算法），其中一种就是用Dijkstra算法写的。《算法导论》的介绍：Dijkstra算法解决的是带权重的有向图上单源最短路径问题，该算法要求所有边的权重都为非负值。

算法思路

1. G集表示所有点集，S集表示已经求解出源到某点的最短路径的点集，V集表示为求出最短路径的点集
2. 首先令S=Ø，V=G

如图所示6个点8条边 V={1,2,3,4,5,6}

1. 取u=1，把点1放入S中，S={1} ,V={2,3,4,5,6}，遍历与点1相连的点，并把权值放入数组

   

   

4.由路径数组可得知此时V集中 点2有最短路径（值为3）所以令u=2，则S={1,2} ,V={3,4,5,6}

因为dis[3]=dis[2]+4 ⇒ 7=3+4 … . dis[5]=dis[2]+9 ⇒ 12=3+9

1. 同理如今S={1,2},V={3,4,5,6},在V中发现dis[3]为除dis[1],dis[2]外的最小值，所以令S=S∪{3}此时S={1,2,3},V={4,5,6}

因为dis[5]=12>dis[3]+1=7+1 ⇒ 令 dis[5]=dis[3]+1=7+1=8 因为dis[6]=∞ >dis[3]+6=7+6 ⇒ 令 dis[6]=dis[6]+6=7+6=13

1. 同理如今S={1,2,3},V={4,5,6},在V中发现dis[4]为除dis[1],dis[2],dis[3]外的最小值，所以令S=S∪{4}此时S={1,2,3,4},V={5,6}