对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点为源点，最后一个顶点为终点。最短路径的算法主要有迪杰斯特拉（Dijkstra)算法和弗洛伊德（Floyd)算法。本文先来讲第一种，从某个源点到其余各顶点的最短路径问题。
这是一个按路径长度递增的次序产生最短路径的算法，它的大致思路是这样的。
比如说要求图7-7-3中顶点v0到v1的最短路径，显然就是1。由于顶点v1还与v2,v3,v4连线，所以此时我们同时求得了v0->v1->v2 = 1+3 = 4, v0->v1->v3 = 1 +7 = 8, v0->v1->v4 = 1+5 = 6。
现在我们可以知道v0到v2的最短距离为4而不是v0->v2 直接连线的5，如图7-7-4所示。由于顶点v2还与v4,v5连线，所以同时我们求得了v0->v2->v4其实就是v0->v1->v2->v4 = 4+1=5，v0->v2->v5 = 4+7 = 11，这里v0->v2我们用的是刚才计算出来的较小的4。此时我们也发现v0->v1->v2->v4 = 5要比v0->v1->v4 = 6还要小，所以v0到v4的最短距离目前是5，如图7-7-5所示。
当我们要求v0到v3的最短路径时，通向v3的三条边，除了v6没有研究过外，v0->v1->v3 = 8, 而v0->v4->v3 = 5 +2 = 7，因此v0到v3的最短路径为7,如图7-7-6所示。
如上所示，这个算法并不是一下子就求出来v0到v8的最短路径，而是一步步求出它们之间顶点的最短距离，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到想要的结果。
程序代码如下：（改编自《大话数据结构》）
C++ Code 输出为：
其中CreateMGraph函数创建出来的邻接矩阵如图7-7-7所示。
相信经过上面的分析，大家可以自己进行循环跑程序分析了，循环结束后final = { 1, 1, 1, 1, 1, 1, 1, 1, 1 }表示所有顶点均完成了最短路径的查找工作。此时D = { 4, 3, 0, 3, 1, 4, 6, 8, 12 }, 注意我们在前面说过Dijkstra算法可以求某个源点到其他顶点的最短路径，现在我们上面程序中给出的pos = 2, 即源点为v2, 所以D[2] = 0 表示没有到自身的路径。D数组表示v2到各个顶点的最短路径长度，比如D[8] =1+2 + 3 + 2 + 4 = 12。此时P = { 1, 0, -1, 4, 0, 4, 3, 6, 7 }， 可以这样来理解，P[2] = -1 表示v2没有前驱顶点，P[1] = P[4] = 0 表示v1和v4的前驱顶点为源点v2。再比如P[8] = 7,表示v8的前驱是v7；再由P[7] = 6，表示v7的前驱是v6； P[6] = 3 表示v6的前驱是v3, 这样就可以得到v2 到 v8的最短路径为v2->v4->v3->v6->v7->v8，从上面的程序输出也可以验证我们的推测。
其实最终返回的数组D和数组P，是可以得到v2到任意一个顶点的最短路径和路径长度的，也就是说我们通过Dijkstra算法解决了从某个源点到其余各顶点的最短路径问题。从循环嵌套可以得到此算法的时间复杂度为O(n^2)，如果我们要得到任一顶点到其余顶点的最短路径呢？最简单的办法就是对每个顶点都当作源点进行一次Dijkstra算法，等于在原有算法的基础上，再来一次循环，此时整个算法的时间复杂度就为O(n^3)。
