【数据结构第六周】图（下）【最短路径问题】
1、最短路径问题
问题抽象：
在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径 。这条路径就是两点之间的最短路径(Shortest Path) ，第一个顶点为源点(Source)，最后一个顶点为终点(Destination) 。
问题分类：
单源最短路径问题:从某固定源点出发，求其到所有其他顶点的最短路径 。（有向）无权图，（有向）有权图
多源最短路径问题:求任意两顶点间的最短路径
2、 无权图的单源最短路算法
按照递增(非递减)的顺序找出到各个顶点的最短路
dist[W] = S到W的最短距离 （初始化的时候就赋值一个正无穷或者负无穷或者-1）
dist[S] = 0
path[W] = S到W的路上经过的某顶点
void Unweighted ( Vertex S ）
{
Enqueue(S, Q);
while(!IsEmpty(Q))
{
V = Dequeue(Q);
for ( V 的每个邻接点 W )
{
if(dist[W]==-1 )
{
dist[W] = dist[V]+1;
path[W] = V;
Enqueue(W, Q);
}
}
}
}
T = O( |V| + |E| )
3、有权图的单源最短路算法
按照递增（非递减）的顺序找出到各个顶点的最短路
Dijkstra 算法
令S={源点s + 已经确定了最短路径的顶点vi}
对任一未收录的顶点v,定义dist[v]为s到v的最 短路径长度,但该路径仅经过S中的顶点。即路径 {s->(vi属于S)->v}的最小长度 。
每次从未收录的顶点中选一个dist最小的收录(贪心)
增加一个v进入S,可能影响另外一个w的dist值!
dist[w] = min{dist[w], dist[v] + <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> ;
path[W] = V;
}
}
}
}
}
时间复杂度
方法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| ) （适合稀疏图）
4、多源最短路算法
方法1:直接将单源最短路算法调用|V|遍
T = O( |V|^3 + |E|*|V|) （适合稀疏图）
方法2：Floyd算法
T = O( |V|^3 ) （适合稠密图）
Floyd算法
void Floyd()
{
for(i=0;i<N;i++)
{
for( j = 0; j < N; j++ )
{
D[i][j] = G[i][j];
path[i][j] = -1;
}
}
for( k = 0; k < N; k++ )
{
for( i = 0; i < N; i++ )
{
for( j = 0; j < N; j++ )
{
if( D[i][k] + D[k][j] < D[i][j] )
{
D[i][j] = D[i][k] + D[k][j];
path[i][j] = k;
}
}
}
}
}