最短路径问题
最短路径问题的抽象：在网络（带权的图）中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径。
问题分类：
单源最短路径问题：
从固定顶点出发，求其到所有其他顶点的最短路径。（可分为有无权值）
多源最短路径问题：
求任意两顶点间的最短路径。
（有权无权都一样）；
无权图的单源最短路算法
算法思路：按照递增（非递减）的顺序找出到各个顶点的最短路，由于无权值，所以可以直接用BFS。
算法伪码：
//dist数组代表S到W的最短路径，全部初始化为0即可
//path [W] 代表S到W的路上经过的某点，当输出路径时一步步往前推即可输出正确的路径
//时间复杂度T=O(V+E);
void Unweighted (vertex S)
{
Enqueue(S,Q);
while(!IsEmpty(Q)){
V = Dequeue(Q);
for(V的每个邻接点W){
if(dist[W]==0){
dist[W] = dist[V]+1;
path[W]= V;
Enqueue(W,Q);
}
}
}
}
算法代码
/* 邻接表存储 - 无权图的单源最短路算法 */
/* dist[]和path[]全部初始化为-1 */
void Unweighted ( LGraph G, int dist[], int path[], Vertex S ) {
Queue Q;
Vertex V;
EdgeNode W;//EdgeNode为边表结点
Q = CreateQueue( G->numnodes );
dist [S] = 0;
AddQ(Q,S);
while(!IsEmpty(Q)){
V = Dequeue(Q);
for(W = G->adjList[V]->firstedge;W;W=W->next;){
if(dist[W->adjvex]==0){
dist[W->adjvex] = dist[V]+1;
path[W->adjvex]= V;
addQ(Q,W->adjvex);
}
}
}
}
有权图的单源最短路算法
由于带有权值，如果只用bfs的话，不能够保证bfs到的这一条路最短，两点之间如果有多条道路能连通，bfs只能找到随机一条，而我们必须确保这一条最短，于是这里的算法思路是：按照递增的顺序找出到各个顶点的最短路，核心算法思想应该是递推和贪心。
算法介绍：Dijkstra 算法
令S为一个{源点s + 已经确定了最短路径的顶点vi}的集合，
对任一未收录的顶点v，定义dist[v]为s到v的最 短路径长度，但该路径仅经过S中的顶点。
1：若路径是按照递增（非递减）的顺序生成的，则真正的最短路必须只经过S中的顶点 （画一个有三个结点的图即可证明）
2：每次从未收录的顶点中选一个dist最小的收录（贪心）
3：每收录一个V进入S，可能影响另外一个w的dist值！但是此处只考虑这个V周围的结点 ，这样最后也能把所有的情况考虑到而且很方便。则： dist[w] = min{dist[w], dist[v] + <v,w>的权重}
算法伪码：
//collected []数组代表是否被收录，初始值都为false。
//dist数组的初始值都为max，除了源点的为0。
void Dijkstra( Vertex s )
{
while(1){
V = 未收录的结点中dist值最小的那一个；
/*
这一步有两种方法，各自的时间复杂度不同。
1：直接遍历所有未遍历结点找出最小值：T= O( |V|2 + |E| )稠密图更好
2：利用最小堆储存dist的值：T= O( |V| log|V| + |E| log|V| ) = O( |E| log|V| )稀疏图更好
*/
if(V==NULL)break;
collected [V] =true ;
for(V的每一个邻接点W){
if ( dist[V]+E<V,W> < dist[W] ) {
dist[W] = dist[V] + E<V,W> ;
path[W] = V;
}
}
}
} /* 不能解决有负边的情况 */
算法代码：
/* 邻接矩阵存储 - 有权图的单源最短路算法 */
Vertex FindMinDist( MGraph Graph, int dist[], int collected[] )
//此处采用的是直接遍历所有结点
{
Vertex W;
int mindist=INFINITY;
Vertex minVertex;
for(W=0;W<Graph->numnodes;W++){
if(collected[W]==false && dist[W] < mindist){
mindist = dist[W];
minVertex = W;
}
}
if(mindist<INFINITY)return minVertex;
else return ERROR;
}
bool Dijkstra( MGraph Graph, int dist[], int path[],Vertex S )
{
bool collected [ Graph->numnodes];
Vertex V, W;
//进行dist数组和collected数组的初始化
for ( V=0; V<Graph->numnodes; V++ ) {
dist[V] = Graph->Graph->G[S][V];
if ( dist[V] <INFINITY ) //说明两点之间有直接连通的边
path[V] = S;
else path[V] = -1;
collected[V] = false;
}
dist[S] = 0;
collected[S] = true;
while(1){
V = FindMinDist(Graph,dist,collected);
if(V==ERROR)break;
collected [V] =true ;
for(W = 0;W<G->numnodes;W++){
if(collected[W]==false &&Graph->G[V][W]<INFINITY){//未收录且有相连边
if ( Graph->G[V][W]<0 ) /* 若有负边 */return false;
if ( dist[V]+Graph->G[V][W] < dist[W] ) {
dist[W] = dist[V] +Graph->G[V][W] ;
path[W] = V;
}
}
}
return true;
} /* 不能解决有负边的情况 */
多源最短路径问题
方法1：直接将单源最短路算法调用|V|遍
T= O( |V|3 + |E||V|)
方法2：Floyd算法
T= O( |V|3 )
Floyd算法
利用了动态规划的思想，设置一个DP [i] [j]，表示从i到j的最短路径。
DP数组的初始化：连通的路初始值和邻接矩阵一样，未连通的路DP[i][j]设为max。
动态规划的关系式：DP[i][j] = min(DP[i][k] + DP[k][j],DP[i][j]);(其中K代表此时能经过的结点，K的值从0到N-1)
算法源码：
//邻接矩阵表示
//path [i][j] 还是一样用来存储上一个经过的结点
bool Floyd(MGraph Graph, WeightType DP [ ][MaxVertexNum], Vertex path[ ][MaxVertexNum])
{
//初始化
for(int i = 0;i < Graph->numnodes;i++){
for(int j = 0 ;j <Graph->numnodes;j++){
if(G[i][j] == INFINITY)DP[i][j] = INFINITY;
else DP[i][j] = G[i][j]
path[i][j] = -1;
}
}
for( int k = 0; k < Graph->numnodes; k++ ){
for(int i = 0; i < Graph->numnodes; i++ )
for(int j = 0; j < Graph->numnodes; j++ )
if(DP[i][j]<0)return false ;
if( DP[i][k] + DP[k][j] < DP[i][j] ) {
DP[i][j] = DP[i][k] + DP[k][j];
path[i][j] = k;
}
}
return true;
}