最短路学习笔记

---

图的存储

邻接矩阵

    初始化 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次，则有负环.

---

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

如有不足或错误欢迎交流