关于图的最短路径问题，是图这种数据结构中的经典问题。也是与我们的生活息息相关的，比如上海四通八达的地铁线路，从一个地铁站，到另一个地铁站，可能有很多种不同的路线。那么，我们选哪种路线，用时最短？换乘最少？花费最少？
目标不同，选择的方案可能不一样。简单的图形网络，可以靠我们的经验和感觉，但是复杂的道路，或者地铁网络，需要计算机来帮我们提供最佳的方案。比如现在出行必备的百度地图，外卖软件上给骑手做的路线规划，都是通过各种算法，做出最合理的安排，也叫最短路径。
如上面的地铁路线图所示，这个路线图通过前面的学习，可以抽象为一个加权图。根据我们的目标不同，两个站点之间的权重可以设置为不同的值，比如追求时间最短，那我们两个站点之间的权重可以是这一段路程地铁运行耗费时间。这样当我们选定出发点（也叫源点）和终点后，通过计算不同路径的权重和，得到不同方案的最终权重，最终找到一种最省时间的方案。也就是计算两点之间的最短路径。
迪杰斯特拉算法简单来说是按照路径长度的递增的次序，产生最短路径的算法。下面我们推演一下算法计算过程：
- 如果求V0到V1的最短距离，很明显答案就是1，路径是V0到V1的连线
- 同时，可以看到顶点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-V1-V2，而不是V0到V2的直线距离
- 由于顶点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还要小。所以到v4目前的最小距离是5
- 当我们要求V0到V3的最短距离时，通向v3的三条边，除了V6没有研究过外，V0-V1-V3的结果是8，而V0-V4-V3=5+2=7。因此到v3的最短距离是7
- 可以看到，它并不是一下子就求出了vo到v8的最短路径，而是一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到你要的结果。
2.2.1 构造邻接矩阵
我们先将上面的路线图，通过邻接矩阵保存下来，方便后续计算使用。
2.2.2 算法实现
输出结果为：
在求解图的最短路径的方法中，最朴素的方法是：以图中每个顶点为源点共调用n次算法。这种计算时间复杂度是O(n^3)。 那么实际上，还有一种算法，时间复杂度还是O(n^3)，这就是弗洛伊德算法。相对于常规求解，弗洛伊德的优势是形式上会简单一点。
- 利用二维数组dist[i][j]记录当前vi到vj的最短路径长度，数组dist的初值等于图的带权邻接矩阵;
- 集合S记录当前允许的中间顶点，初值S={}
- 依次向S中加入v0 ,v1… vn-1，每加入一个顶点，对dist[i][j]进行一次修正：设S={v0 ,v1… vk-1}，加入vk，则dist(k)[i][j] = min{ dist(k-1)[i][j]，dist(k-1)[i][k]+dist(k-1)[k][j]}。
- 其中，dist(k)[i][j]的含义：允许中间顶点的序号最大为k时从vi到vj的最短路径长度。dist(n-1)[i][j]就是vi到vj的最短路径长度。
测试结果：
大话数据结构书籍