7.1 最短路径问题

最短路径问题的抽象

在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径。
这条路径就是两点之间的最短路径（Shortest Path）
第一个顶点为源点（Source）
最后一个顶点为终点（Destination）

问题分类

单源最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径
（有向）无权图
（有向）有权图
多源最短路径问题：求任意两顶点间的最短路径

无权图的单源最短路算法

按照递增（非递减）的顺序找出到各个顶点的最短路

void Unweighted(Vertex S)//以BFS为原型改造的单源无权最短路算法 
{
	Enqueue(S,Q);
	while(!Isempty(Q))
	{
		V = Dequeue(Q);
		for( V的每个邻接点 W )
		{
			if(dist[W] == -1)//如果没有被访问过 
			{
				dist[W] = dist[V] + 1;//初始化源点为0，其他点为-1
				path[W] = V;//记录当前已走过的路径结点，初始化为-1
				Enqueue(W,Q);
			}
		}
	}
}

dist[W] = S 到 W 的最短距离
dist[S] = 0 源点到源点距离为0
path[W] = S 到 W 的路上经过的某顶点
打印路径时顺着path数组一个一个往前推，得到W->S的反向路径，用堆栈来reverse即可
时间复杂度：O（ |V| + |E| ）

有权图的单源最短路算法

Dijkstra算法

令集合S = {源点s + 已经确定了最短路径的顶点vi}
对任一未收录的顶点v，定义dist[v]为s到v的最短路径长度（不一定是最终的最短路径），但 该路径仅经过S中的顶点。即路径{s->(vi∈S)->v}的最小长度
若路径是按照递增（非递减）的顺序生成的，则
真正的最短路必须只经过S中的顶点
每次从未收录的顶点中选一个dist最小的收录（贪心）
增加一个v进入s，可能影响另外一个w的dist值！（v在s->w的路径上并且v->w一定有一条直接的边）

void Dijkstra(Vertex s)
{
	while(1)
	{
		V = 未收录顶点中dist最小者;
		if(这样的V不存在) break;
		collected[V] = true;
		for( V 的每个邻接点 W )
		{
			if(collected[W]==false)
			{
				if(dist[V]+E<V,W> < dist[W])
				{
					dist[W] = dist[V] + E<V,W>;//初始化源点为0，其他点为+INT_MAX
					path[W] = V; //初始化为-1
				}
			}
		}
	}
}//不能解决有负边的情况 

如何获取未收录顶点中dist最小者
法1：直接扫描所有未收录顶点——O（|V|）
T = O(|V|^2 + |E|)——对于稠密图效果好
法2：将dist存在最小堆中——O（log|V|）
更新 dist[w] 的值——O（log|V|）
T = O（ |V|log|V| + |E|log|V| ）= O（ |E| log|V| ）——对于稀疏图效果好