图-最短路径问题
2016-07-03 本文已影响414人
IAmWhoAmI
在网络中,求两个不同顶点之间的所有路径中,边的权值之和最小的那一条路径
- 这条路径是两点之间的最短路径
*第一个顶点为源点
*最后一个顶点为终点
问题分类
- 单源 最短路径问题
从固定源点出发,求其到所有其他顶点的最短路径- (有向)无权图
- (有向)有权图
- 多源 最短路径问题
求任意两顶点见得最短路径
有向无权图的单源最短路径
按照 递增 的顺序找出给定节点到各个节点的最短路径
Paste_Image.pngdist[S] = 0
path[]
public UnWeight(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);
}
}
}
}
有权有向图的单源最短路径
#dijkstra算法
令 S={源点A+已经确定了最短路径的顶点Vi}
对任一未收录的·顶点v·,定义dist[v] = A 到 v 的最短路径长度。
(但该路径仅仅经过集合S中的顶点)。
若路径是按照 @递增 的顺序生成的=>
{
真正的最短路必须只经过集合S中的顶点。(反证法)
每次从未收录的顶点中选一个dist最小的收录(贪心)。
增加v进入S以后,可能影响另外一个未收录节点w的dist值
#(比如之前不可达,或是之前的到达路径比较长==)
# dist[w]=min(dist[v] + E<v,w>, dist[w])
# E<v,w>表示该边的权重
}
Paste_Image.png
#个人BB
一个富有侵略性的算法。
想象顶点就是一个城池。
占据了顶点以后,依据已经占据的城池向外扩展。
首先扩展就是离出发点最近的领土
(始终是计算出发点和其他点的距离)。
后进来的领土会不会影响旧的领土的距离呢?
@不会
为什么?
加进来的点是按距离顺序添加的。
#代码
void Dijkstra(Vertex s){
while(1){
V = 未收录顶点中dist最小者;
if(没有V){
return;
}
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|*|V| + E)
每个节点都要扫一遍。V个点*V
但是其实真是情况是不是,但后面扫的范围会变小呢...因为大部分被加入到了集合collected 中了。
E 是因为要对每个新加入的点的邻接点进行处理,所以每条边都会处理一遍
- 方法2:将dist存在最小堆中-O(log(V)) 适用于稀疏图
- 更新dist[w]的值 - O(log|V|)
- T = O(|N|log|V| + |E|log|V|) = O(|E|log|V|)
多源最短路径问题
#floy算法:
#个人BB
其实和dijkstra有点像。就是不断地添加点到一个集合中。
添加进来的点,
#已经收录的集合到这个点的路径
以及 #这个点到达其他点的路径
暴露了出来。
此时,到达k的路径,以及从k 到达别人的路径保持不变。
改变的是其他要经过k来走最短路径的路。
假设之后,某个点w到k的距离发生了变化,必然是因为加了新的点k1,
那么k1,自然会将 w到k的距离发生变化,而且,会把w经过 k1到达的所有点的距离都会进行改变。
(因为之前,我在担心,k对整个距离产生变化以后,其他点的结果相当于依赖于看k的距离,但是,如果k的距离改变了,那么岂不是其他结果不准了?
其实k距离发生变化,只有可能是有k1加入导致,如果k1导致k发生变化,那么经过k的路径,自然一定要经过k1,
因此k1自然会将所有的后面所能到达的点全部化为更新后的最短路径。
需要多想想。)
public void floyd(){
for(i =0;i<N ;i++){
D[i][j] = G[i][j];
path[i][j] = -1;
}
for(int k=0;k<N;k++){
for(int i =0;i<N;i++){
for(int 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;
}
}
}
}
}
T=O(|V||V||V|)