图-最短路径问题

2016-07-03  本文已影响414人  IAmWhoAmI

在网络中,求两个不同顶点之间的所有路径中,边的权值之和最小的那一条路径

问题分类

有向无权图的单源最短路径

按照 递增 的顺序找出给定节点到各个节点的最短路径

Paste_Image.png
dist[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;
                }
    }
}
/*不能解决有负边的情况*/

如果遇到负值圈,就可能会陷入一直死循环的情况。


负值圈
每个节点都要扫一遍。V个点*V
但是其实真是情况是不是,但后面扫的范围会变小呢...因为大部分被加入到了集合collected 中了。
E 是因为要对每个新加入的点的邻接点进行处理,所以每条边都会处理一遍

多源最短路径问题

#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|)

上一篇下一篇

猜你喜欢

热点阅读