如何用C语言实现Dijkstra算法并输出最短路径？

本文共计1813个文字，预计阅读时间需要8分钟。

某源点到其他顶点的最短路径+这个算法最初心里是怵怵不安的，不知为何，花了好多长时间才弄懂，还写了一篇，又遇到时还是出错，今天再次写它，心里没那么怕了，鼓起勇气研究。

某个源点到其余各顶点的最短路径

这个算法最开始心里怕怕的，不知道为什么，花了好长时间弄懂了，也写了一遍，又遇到时还是出错了，今天再次写它，心里没那么怕了，耐心研究，懂了之后会好开心的，哈哈

Dijkstra算法：

图G

如图：若要求从顶点1到其余各顶点的最短路径，该咋求；

迪杰斯特拉提出“按最短路径长度递增的次序”产生最短路径。

首先，在所有的这些最短路径中，长度最短的这条路径必定只有一条弧，且它的权值是从源点出发的所有弧上权的最小值，例如：在图G中，从源点1出发有3条弧，其中以弧（1，2）的权值为最小，因此，（1，2）不仅是1到2的一条最短路径，并且它可能是源点到其它各个终点的最短路径中的一条子路径。

其次，第二条长度次短的最短路径只可能有两种情况：①它或者只含一条从源点出发的弧且弧上的权值大于已求得最短路径的那条弧的权值，但小于其他从源点出发的弧上的权值②它或者是一条只经过已求得最短路径的顶点的路径。

例如图G中，从1到其他各点。