最短路径问题（MOOC浙大数据结构课程总结）
最短路径问题（MOOC浙大数据结构课程总结）
在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那条路径。
一、 单源最短路径（无权图）
按照非递减的顺序找出到各个顶点的最短路
1、 思路：BFS
设s为源点
dist[w]:s到w的最短距离
dist[s]=0 //源点到自身的距离为0
path[w]=s到w的路上经过的某顶点d
将dist[]数组与path[]数组都初始化为-1
2、 伪代码
3、 源点到终点的步数之和？
因为已经把到达所有顶点的最短路径都求了出来，因为只需确定题目所需的终点是哪个即可。
4、 如何输出路径？
Path[]数组中保存了到达该顶点的前一个顶点的位置。如1-2-3，即path[3]=2,path[2]=1,path[1]=-1，（因为一开始将path初始化为-1，所以以源点为下标对应的值为-1）。可以发现这是逆序的过程，因此先讲经过的值压入堆栈，遇到-1时结束，最后再输出。
二、 单源最短路径（有权图）
按照非递减的顺序找出到各个顶点的最短路
1、 Dijkstra算法
2、 过程示例
定义collected[]数组，初始化为false，即全部都没被收录。
定义dist[]数组初始化为正无穷，path[]初始化为-1.假设顶点1为源点，则dist[1]=0
与源点直接相邻的两个顶点，它们到源点的最短距离就是边的权重，因此dist[2]=2,path[2]=1,dist[4]=1,path[4]=1;
此时只有v1被收录。Collected[1]=true;
此时才进入Dijkstra算法。将源点传进去。
在未收录的顶点中选取dist最小值的下标，如果不存在就退出。
以此题为例，dist最小值的下标是4，因此collected[4]=true; 对4的每个邻接点，即3567，我们先看3。3没有被收录，且1到4的距离+4到3的距离<dist[3]，因此dist[3]的距离更新为1到4的距离+4到3的距离。保存路径，path[3]=4;到此为止，我们完成了对3的处理。
接下来再从未收录顶点中找dist最小值，我们看到是2，接下来的处理过程类似，以此类推。
3、 如何找到未被收录中dist的最小值？
（1） 遍历
（2） 用最小堆实现（先把dist数组中的元素都压入最小堆）
4、 源点到终点的权重和
因为已经把到达所有顶点的最短路径都求了出来，因为只需确定题目所需的终点是哪个即可。
5、 路径输出：与上种情况类似。
6、 伪代码
三、 多元最短路径（求任意两顶点间的最短路径）
1、 Floyd算法
用邻接矩阵存储。先将邻接矩阵初始化为正无穷，对角线初始化为0。如果两个顶点之间有直接边，则初始化为它们的权重。
2、 伪代码
3、 源点到终点的权重和
D[i][j]为顶点i到顶点j的最小权重和。如果D[i][j]为正无穷，说明没有从顶点i到顶点j的路径。
4、 路径输出
路径保存在path[][]数组中。Path[i][j]=k，即顶点i到j经过k。再求path[i][k]…递归输出