随着2020的即将到来,似乎越来越忙了(hh,当然不是忙于准备年货,而是忙于补各种作业).
今天下午难得有段闲暇时光,复习一下(之前就没理解透透的吧) 图论中的最短路部分,以
便更好的学习.
最短路算法:
1、Dijkstra（一般）: 通过每次循环找全局最小值进行更新其他节点(时间复杂度:O(n^2))
   Dijkstra（优化）：通过二叉堆(优先级队列)找最小值(队首如果就是最小值的话,我们就不用每次都去寻找最小值了)
                     (时间复杂度:O(mlog(n))
2、Bellman-Ford    ：(后续补充,先学了SPFA,hhhhh)
3、SPFA(Bellman-ford的优化) : 通过队列(类似于BFS,每个点可能出队、入队多次)来实现每个顶点的更新,直到队列
                     为空为止.
                     (时间复杂度(km),其中 k 是一个较小的常数)
4、Floyd（任意两点间的最短路）:
                      (时间复杂度:O(n^3)

下面逐个介绍一下各个算法及实现代码:

1、Dijkstra： 
  优点:优化后的算法时间复杂度相对于其他算法来说较低
  缺点:无法处理有负边权的图(这是重点),也就是目光短浅,具体怎么短浅稍后细说.
  算法流程:
  1、初始化dist[1] = 0,(因为本身到自己的距离是 0 ),其余节点的设置为正无穷大(memset(dist,0x3f,sizeof(dist));
  2、找出一个**未被标记的**、dist[x]最小的节点 x ,然后标记节点 x.
  3、扫描节点 x 的所有出边(x,y,z),也就是所有跟节点 x 相连的边,若dist[y] > dist[x] + z,则使用dist[y] = dist[x] + z进行更新,dist[y].（这里用到了三角不等式的原理）.
  4、重复上述2 ~ 3 个步骤,直到所有节点都被更新.
  用图来理解更清晰:

具体看这位大佬的图解: https://www.acwing.com/blog/content/462/ （十分详细）

  （懒得画了,hhhhhhh）
  为啥不能处理负权?
  首先我们要清楚一个点:Dijkstra是每次贪心的选择跟当前邻接的点,而不会去考虑处邻接之外的其他点,举个例子来说:

    8
  A ---- B
  |    /
  |   /
10|  / -4
  | /
  C

从 A -- > B 我们可以很明显看出最短路径是 A - > C - > B （10 + （-4）） = 6;
  但是通过Dijkstra算法我们得到的结果是 A - > B （8）,答案是 8;
  (可以自己试一下)
  因为我们从起点 A 开始,最先开始找的是 A -> B 所花费的路径短还是 A -> C 花费的路径短,当到 B (第一次选择的结果,就会从B开始在找与B相关的最短的边)(所以如果我们用Dijkstra来处理有负权值得图时得到得答案很可能是不正确的).

代码部分(一般): 题目链接: https://www.acwing.com/problem/content/851/
（需要修改一下输出才能AC哦）

    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<string.h>
    #include<cstdio>
    #include<string>
    #define INF 0x3f3f3f3f                           // 表示最大值
    using namespace std;
    const int maxn =505;
    int a[maxn][maxn],vis[maxn],dist[maxn];          // 采用邻接矩阵来存图(消耗得内存较大)
    int n,m;
    int main(void) {
        void Dijkstra();
        memset(a,0x3f,sizeof(a));
        memset(dist,0x3f,sizeof(dist));              // 一定要记得初始化为正无穷大 
        memset(vis,0,sizeof(vis));                   // 标记
        scanf("%d%d",&n,&m);
        int x,y,w;
        for(int i = 1; i <= m; i ++) {
            scanf("%d%d%d",&x,&y,&w);
            a[x][y] = min(a[x][y],w);                // 可能会有重边(重复的边),所以需要取最小值
        }
        Dijkstra();
        for(int i = 1; i <= n; i ++ ){
            printf("%d\n",dist[i]);
        }
        return 0;
    }
    void Dijkstra() {
        int x = 0;                           // 用来记录每次全局最小值得下标
        dist[1] = 0;                         // 刚开始与自身的距离是 0 
        for(int i = 1; i < n; i ++) {        // 循环 N - 1 次(因为起点已经更新了,还剩下 N - 1 个点未更新)
            x = 0;
            for(int j = i; j <= n; j ++) {
                if(vis[j] == 0 && (x == 0 || dist[j] < dist[x])) { // 选取未标记过的全局最小值
                    x = j;
                }
            } 
            vis[x] = 1;                      // 标记已选中的顶点
            for(int j = 1; j <= n; j ++) {   // 更新与该顶点相关的边
                dist[j] = min(dist[j],dist[x] + a[x][j]);
            }
        }
        return ;
    }

Dijkstra(优化) ：（采用邻接表的存储方式来存图(模拟数组链表的方式)）

题目链接: https://www.acwing.com/problem/content/852/
（需要修改一下输出才能AC哦）

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 1e5 + 6;
priority_queue<pair<int,int> >pq;                        //优先级队列默认是从大到小进行排序的(我们每次插入队列中这个数的相反数,自然就能表示这个数的最小值)
int vis[maxn],head[maxn],Next[maxn],edge[maxn],ver[maxn];
int dist[maxn];
int n,m,tot;
int main(void) {
    void Dijkstra();
    void add(int x,int y,int w);
    int x,y,w;
    memset(vis,0,sizeof(vis));
    memset(dist,0x3f,sizeof(dist));
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= m; i ++) {
        scanf("%d%d%d",&x,&y,&w);
        add(x,y,w);
    }
    Dijkstra();
    for(int i = 1; i <= n; i ++ ){
        printf("%d\n",dist[i]);
    }
    return 0;
}
void add(int x,int y,int w) {
    ver[++tot] = y,edge[tot] = w;        // ver[]:表示每条边的终点,edge[]:表示每条边的权值
    Next[tot] = head[x],head[x] = tot;   /* Next[]:存储上一条边的序号,用来进行连接(遍历)
    插入到表头                              表示从相同节点出发的下一条边在ver和edge数组中的存储位置 
                                          */
    return ;                             // head[]:记录从每个节点出发的第一条边在ver 和 edge 数组中的存储位置
}
void Dijkstra() {
    dist[1] = 0;
    pq.push(make_pair(0,1));             // first:权值大小,second:该权值对应的节点
    while(pq.size()) {
        int x = pq.top().second;pq.pop();
        if(vis[x]) continue;
        vis[x] = 1;
        // 遍历与该节点相关的所有边(更新)
        for(int i = head[x]; i ; i = Next[i]) {
            int y = ver[i],z = edge[i];
            if(dist[y] > dist[x] + z) {
                // 将更新后的最小值(值和对应的节点)组合重新插入到队列中,以便于后面寻找更小的(每次都要是最小距离)
                dist[y] = dist[x] + z;
                pq.push(make_pair(-dist[y],y)); 
            }
        }
    }
    return ;
}

2、SPFA（）算法:
   优点:SPFA()算法最大的优点莫过于可以处理负边权,而且优化过后的时间复杂度与Dijkstra()算法相差不大
   缺点:仅用队列实现的SPFA算法时间复杂度还是有点高的,因为它每次顶点可能会多次进行出队、入队、这也就是它可以      处理负边权的最大原因。
   算法流程:
   1、建立一个队列,最初队列只包含起点 1
   2、取出队头节点x,扫描它的所有出边(x,y,z),若dist[y] > dist[x] + z,则使用dist[x] + z更新dist[y].同时，若
   y 不在队列中,则把 y 入队,并且进行标记.
   3、重复上述步骤,直到队列为空。
   该算法的队列都保存了待扩展的节点(这点也很重要,可以拿上面的例子模拟一下).每次入队都相当于完成一次dist数组的更新操作,使其满足三角形不等式.
   一个节点可能会出队、入队多次。最终，图中节点收敛到全部满足三角形不等式的状态。
   代码部分:

题目链接: https://www.acwing.com/problem/content/853/
（需要修改一下输出才能AC哦）

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<string.h>
#include<string>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 1e5 + 5;
int head[maxn],Next[maxn],edge[maxn],ver[maxn];
int dist[maxn],vis[maxn];
int n,m,tot;
int main(void) {
    void add(int x,int y,int w);
    void spfa();
    memset(dist,0x3f,sizeof(dist));
    memset(vis,0,sizeof(vis));
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= m; i ++) {
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        add(x,y,w);
    }
    spfa();
    for(int i = 1; i <= n; i ++) {
        cout<<dist[i]<<endl;
    }
    return 0;
}
void add(int x,int y,int w) {
    ver[++tot] = y,edge[tot] = w;
    Next[tot] = head[x],head[x] = tot;
    return ;
}
void spfa() {
    queue<int>q;
    dist[1] = 0,q.push(1);
    vis[1] = 1;
    while(!q.empty()) {
        int x = q.front();
        q.pop();
        vis[x] = 0;                              // 出队后就标记为未使用过
        for(int i = head[x]; i ; i = Next[i]) {
            int y = ver[i],z = edge[i];
            if(dist[y] > dist[x] + z) {
                dist[y] = dist[x] + z;           // 这里只要符合三角式定理，就更新
                if(vis[y] == 0) {
                    q.push(y);                   // 每次入队的是未标记过的顶点
                    vis[y] = 1;                  // 入队后就标记已使用了
                }
            }
        }
    }
    return ;
}