最短路学习笔记

作者: MayFlyyh 分类: 学习笔记, 最短路 发布时间: 2018-02-13 22:17 ė 6 1条评论

图的存储

邻接矩阵

    初始化 G[i][j]=inf
    G[i][j] = v 表示 从点i与点j有边,权值为v;
    有向图存一遍,无向图存两遍,重边取最小(吧)
    适用于稠密图

领接表

定义一个Last[N]数组用于存储某点最新连接的边号

int Last [N],cnt = 0;
struct Edge{
    int to,v,next;
} E[M] ;

加边:

    inline void add (int from,int to,int v) {
        cnt++;
        E[cnt].next = Last [from];
        Last [from] = cnt;
        E[cnt].to = to;
        E[cnt].v = v;
    }

适用稀疏图

注意,在无向图中,领接表存储边的数组应开到双向边的2倍


inf表示一个极大值;


1. Floyd-Warshall

时间复杂度O(n^3) 空间复杂度O(n^2)

一般使用邻接矩阵实现
初始化时,任意两条路为无现长(极大,但应使该值得两倍不超过int范围)。
与自己连接的长度为0

    int G[MAXN][MAXN];
    for(int k=1;k<=N;++k)
        for(int i=1;i<=N;++i)
            for(int j=1;j<=N;++j)
                G[i][j]=std::max(G[i][j],G[i][k]+G[k][j]);

理解:

如果求从A至B的最短路,不断寻找一个点K,使得从A到K,再从K到B的总路程最短。

Floyd-Warshall算法不能解决带有“负权回路”(或者叫“负权环”)的图

因为带有“负权回路”的图没有最短路

但可以解决带有负权的问题


## 2.Dijkstra

时间复杂度(N^2) 空间复杂度(M)

初始化 (以下初始化默认为此方式):

   Last[N],E[M];
int From                  //出发点的编号
int v[N]                  //记录该点是否已经使用
int dist[N]               //表示出发点至各点的距离;
for(int i=1;i<=n;i++) dist[i]=inf;
dist[From]=0;
for(int i=Last[From];i;i=E[i].next){
    int To=E[i].to;     //所连接的点
    dist[To]=E[i].v;
}

寻找最短路:

for(int q=1;q<=n-1;++q){
    int min=inf;         //初始化最小值
    int M;               //记录目前最短路的
    for(int i=Last[From];i;i=E[i].next){
        int To=E[i].to;
        if(min>dis[To]&&!v[To]){
            min=dis[M=To];
            v[To]=1
        }
    }
    for(int i=Last[M];i;i=E[i].next){
        int To=E[i].to;
        dis[To]=std::min(dis[To],dis[M]+E[i].v);
    }
}

理解:

1.将点分为两部分

(1).已知最短路径的集合P 
(2).未知最短路径的集合Q

2.在点P中寻找一个点M与From点的距离最短,并将M标记;

3.以M为出发点,将从M出发连接的点i的距离E[i].v加上dis[M]的距离,如果比dis[ i]小,即将新距离视为为From到i的最短距离

4.重复 2~3 n-1次 (最短路中共有n-1条边(最多为n-1次,实际起作用的可能更少);

对于边数M小于N2的稀疏图,是用领接表较优,反之适用邻接矩阵

不可以对具有负权的图使用

堆优化

最优复杂度 ((N+M)logN)

维护堆kogN 边历图N+M

初始化与上文相同

struct heap{
    int node,v;
    bool operator < (const heap &M) const{
        return v>m.v;
    }
priority_queue<heap> q;
q.push((heap){From,0);
while(!q.empty()){
    heap Now=q.top();q.pop();
    int M=Now.node,V=Now.v;
    if(v[M]) continue;
    v[M]=1;
    for(int i=Last[M];i;i=E[i].next){
        int To=E[i].to;
        if(dis[To]>dis[M]+E[i].v){
            dis[To]=dis[M]+E[i].v;
            q.push((heap){To,dis[To]);
        }
    }
}

在朴素的Dijkstra算法中,我们使用大量时间寻找目前与From最短距离的点,这一需求可以使用最小堆实现。


3.Bellman-Ford

时间复杂度(NM) 空间复杂度(M)

在存边中存入始发点的信息

struct Edge{
    int from,to,next,v;
}E[M];

寻找最短路

for(int i=1;i<=N-1;++i){
    for(int j=1;j<=cnt;++j){
        int From=E[j].from,To=E[j].to,V=E[j].v;
        if(dis[To]>dis[From]+V)
            dis[To]=dis[From]+V;
    }
}

检测负回路

for(int j=1;j<=cnt;++j){
        int From=E[j].from,To=E[j].to,V=E[j].v;
        if(dis[To]>dis[From]+V)
            dis[To]=dis[From]+V;
}

理解

通过查看第i条边,验证能否通过第i条边使出发点到To的距离缩短

如果在更新N-1后仍可以更新最短路,那说明存在负回路

关于最短路中回路的讨论

如果最短路中存在正回路,那说明至少有一条边走过两次
若只走一次比会得到比当前包含正回路的最短路更短的方案

如果最短路中存在负回路,那可以通过无限通过负回路使最短路变为无限小,无限小的最短路即不存在最短路

关于N-1的讨论

一个最短路中最多有N-1条边(最小生成树)

最短路与最小生成树的区别

最小生成树是计算从一节点到另一节点的最小边集;

最短路是带权路径,计算权值最小

最小生成树要经过每一个点,

最短路只需要能达到某两点,路径权值最小即可。


3 (2). SPFA

最劣时间复杂度(NM) 空间复杂度(M)

期望时间复杂度:O(kM), 其中k为所有顶点进队的平均次数,可以证明k一般小于等于2

queue<int> q;
q.push(k),v[k]=1,dis[k]=0;
while(!q.empty()){
    int Now=q.front();q.pop();v[Now]=0;
    for(int i=last[now];i;i=e[i].next){
        if(dis[E[i].to]>dis[Now]+E[i].v){
            dis[E[i].to]=dis[Now]+E[i].v;
            if(!E[e[i].to]) 
                q.push(e[i].to),v[e[i].to]=1;
        }
    }
}
理解

如果一个点进入队列N次,那么该图必存在负环

一个顶点在出队后可能再被放入队列,也就是当一个顶点的最短路程估计值变小后,需要对其所有出边进行松弛

但是如果这个顶点最短路程估计值再次变小,仍需要对其所有出边进行松弛,才能保证相邻顶点最短路程同步更新。

所以只有在前一遍松弛中改变了最短路程的顶点,才可能通过该顶点出边所连接的顶点的最短路更新。

使用队列存储,便可以记录在前面松弛中改变了最短路的顶点。
降低了复杂度

其他

SPFA算法有两个优化策略SLF和LLL

SLF:Small Label First 策略,设要加入的节点是j,队首元素为i,若dist(j)<dist(i),则将j插入队首,否则插入队尾;

LLL:Large Label Last 策略,设队首元素为i,队列中所有dist值的平均值为x,若dist(i)>x则将i插入到队尾,查找下一元素,直到找到某一i使得dist(i)<=x,则将i出队进行松弛操作。

SLF 可使速度提高 15 ~ 20%;SLF + LLL 可提高约 50%。

在实际的应用中SPFA的算法时间效率不是很稳定,为了避免最坏情况的出现,通常使用效率更加稳定的Dijkstra算法。


比较

Floyd Dijkstra Dijkstra(heap) Bellman-Ford SPFA
稠密图 与顶点相关 稠密图 与顶点相关 稠密图 与顶点相关 稀疏图 与边关系密切 稀疏图 与边关系密切
可以解决负权 无法解决负权 无法解决负权 可以解决负权 可以解决负权

Dijkstra:O(n2)适用于权值为非负的图的单源最短路径,用斐波那契堆的复杂度O(M+NlogN),

BellmanFord:适用于权值有负值的图的单源最短路径,并且能够检测负圈,复杂度O(MN)

SPFA:适用于权值有负值,且没有负圈的图的单源最短路径,论文中的复杂度O(kE),k为每个节点进入Queue的次数,且k一般<=2,但此处的复杂度证明是有问题的,其实SPFA的最坏情况应该是O(MN).

Floyd:每对节点之间的最短路径。Floyd-Warshall算法的时间复杂度为O(N^3),空间复杂度为O(N^2)。

先给出结论:

(1)当权值为非负时,用Dijkstra。

(2)当权值有负值,且没有负圈,则用SPFA,SPFA能检测负圈,但是不能输出负圈

(3)当权值有负值,而且可能存在负圈,则用BellmanFord,能够检测并输出负圈。

(4)SPFA检测负环:当存在一个点入队大于等于V次,则有负环.


本文借鉴了部分网络博客与《啊哈,算法》的内容

如有不足或错误欢迎交流

本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/37

一条评论

  1. Radiance 2019年1月2日 下午6:40 回复

    %%%

Radiance进行回复 取消回复

电子邮件地址不会被公开。

Captcha Code

Ɣ回顶部