算法研究：最短路径之迪杰斯特拉算法

对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点为源点， 最后一个顶点为终点。最短路径的算法主要有迪杰斯特拉（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的最短路径，而是一步步求出它们之间顶点的最短距离，过程中都是基于 已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到想要的结果。