单源最短路径
基于贪心(在路径值无负权情况下)
复杂度 O(N^2) （邻接矩阵）adjacency matrix
复杂度 O((M+N)logN) （邻接表）adjacency list
当图中路径较少时（m < n^2）(稀疏图)，使用邻接表更优
寻找dis[ ]中最小值的时候如果用C++ STL中的优先队列priority_queue可以优化常数。
本文主要研究基于C语言的最短路算法，暂不占用过多篇幅实现二叉堆排序

思路: 求A点到所有其他点的最短路径。重复以下步骤 : 找出离A最近的点B，通过B点对其他点进行松弛(当前A,B点间距肯定已经是最短的了，因为它无法通过其他点进行松弛)(无负权)。

邻接表

邻接表的存储
类似链表, 这里通过结构体实现, 假设路径数量 m<1000, 结点数 n<300

typedef struct node{
    int u, v, w;                     //使用该结构体存放读取的路径
}node;                               //u起始点 v终点 w路径权值
node road[1000];

再定义两个数组来模拟链表
first[]的键名表示结点，键值表示路径编号
next[]的键名表示路径编号，键值表示路径编号
它们一般定义为全局数组，初始值为0。

int first[300];//first[u]存放以u号结点为起始点的首条路径(读取时反向存放)
               //所以该数组空间应该大于等于结点数 n
int next[1000];//next[i]存放i号路径的下一条路径,这两条路径起始点相同
               //所以该数组空间应该大于等于边数 m

读取路径时如何存放

cin >> road[i].u >> road[i].v >> road[i].w; //读第i条路径的起始点,终点,权值
next[i] = first[road[i].u];
first[road[i].u] = i;

这里是反向存放，把最后读取的边当作第一条，在first[ ]中。
邻接表存放有点绕，尝试解释一下
读第i条边时的处理方法：
first[road[i].u]存放的是以road[i].u这个结点为起始点的上一条路径的路径编号(不妨记为i')(如果现在读取的这条边是以该结点为起始点的第一条路径,那么由于该数组是全局数组，first[road[i].u]的值为0,即i'==0)。现在把这条路径的编号赋给next[i]，表示路径i的下一条路径为i', 然后把i赋给first[road[i].u]。

邻接表的遍历

当要遍历以结点u为起始点的路径时，从first[u]出发,first[u]存放了第一条边，然后不断获得 next[边号]即可

int head = first[u];
while(head != 0) 
{
  --- 对该边进行操作 ---
  head = next[head];
}

Dijkstra(邻接表)核心代码

for(int i=1; i<n; i++)
    {
        int min_w = 0x7fffffff;                   //寻找剩余结点中离目标结点(1号结点)最近的
        int tar = 0;                              //结点编号，初始化为0
        for(int j=2; j<=n; j++)                  //如果找完一趟后还是0，代表剩下的节点都不能与1相连了
        {
            if(!book[j] && dis[j] < min_w)        //book[j]为 1代表已经利用过
            {
                tar = j;
                min_w = dis[j];
            }
        }
        if(tar)
        {
            book[tar] = 1;
            int head = first[tar];
            while(head)
            {
                int nv = road[head].v;
                int nw = road[head].w;
                if(dis[nv] > nw + dis[tar])
                    dis[nv] = nw + dis[tar];
                head = last[head];
            }
        }
        else
            break;
    }

两种方法的核心代码比较类似，变量代表的含义基本相同

Dijkstra(邻接矩阵)核心代码

 for(int i=1; i<n; i++)
    {
        int min_w = 0x7fffffff;
        int tar = 0;                         
        for(int j=2; j<=n; j++)
        {
            if(book[j] == 0 && map[1][j] < min_w)
            {
                tar = j;
                min_w = map[1][j];
            }
        }
        book[tar] = 1;
        if(!tar) 
            break;
        for(int j=2; j<=n; j++)
        {
            if(book[j] == 0)
            {
                if(map[1][j] > map[1][tar] + map[tar][j])
                {
                    map[1][j] = map[1][tar] + map[tar][j];
                }
            }
        }
    }

3. Bellman-Ford

该算法的思路和代码量都比较简短。
可以是看作牺牲一部分复杂度Dijkstra的基础上能够判断处理负权，判断负权环。
对有一张有n个点，m条边的有向图, 用数组dis[ ]保存源点到各点的最短距离，可以通过对边进行 n - 1 次的遍历，当其满足dis[v] > dis[u] + w的时候，就对其进行松弛更新操作，重复n-1次以后就能得到答案，如果n-1次以后还能继续更新，则可以判断图中出现了负权环。

for(int i=1; i<n; i++)             //最多进行 n-1 次
{
    bool checked = 0;    //用checked判断这次循环有无进行松弛操作，若无，则直接退出    
    for(int j=1; j<=m; j++)      //使用每条边尝试松弛
    {
        if(dis[road[j].v] > dis[road[j].u] + road[j].w)
        {
            checked = 1;
            dis[road[j].v] = dis[road[j].u] + road[j].w;
        }
    }
    if(!checked)
        break;
}

4.SPFA

SPFA在Bellman-Ford的基础上加以改进
再Bellman-Ford算法中一方面每次循环不需要对所有边进行松弛判断，只需要对上次松弛操作时成功松弛的结点延伸出的边再进行松弛判断。
因此我们加上队列，让成功松弛的结点进入队列。(类似于广搜的思想。但由于在存在 n 个结点的有向图中, 对于任意结点 i ，在 n-1 次操作之前，即使该结点被成功松弛，亦不一定为最短路径，可能在后面又被更新。所以一个结点可能进入该队列不止一次。这一点区别于普通BFS。
由于是针对每个结点的操作，在稀疏图中(这也是大部分我们所遇到的情况)使用邻接表较方便

SPFA代码(放上全文,一方面SPFA是应用得最多的单源最短路算法,另一方面之前写的时候遇到了点小bug,调试了好久, 长个记性)

#include<iostream>
#include<cstring>
using namespace std;
int n, m;                  // n<=100, m<=1000
typedef struct node{
    int u, v, w;
}node;
node road[1000];
int first_road[100], next_road[1000];    //邻接表
int queue[1000];                  //实现队列
int times[100];                   //每个点进入队列次数
bool book[1000];  
int dis[100];     
bool flag;                        //判断负环               
int main()
{
    cin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        cin >> road[i].u >> road[i].v >> road[i].w;
        next_road[i] = first_road[road[i].u];
        first_road[road[i].u] = i;
    }
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    int head = 0, tail = 1;
    queue[head] = 1;
    book[1] = 1;
    times[1]++;
    while(head < tail)
    {
        int now = queue[head];            //结点
        int bian = first_road[now];       //遍历该结点的路径
        while(bian)
        {
            if(dis[road[bian].v] > dis[road[bian].u] + road[bian].w)
            {
                dis[road[bian].v] = dis[road[bian].u] + road[bian].w;
                int next_node = road[bian].v;
                if(book[next_node] == 0)
                {
                    if(times[next_node] >= n)
                    {
                        flag = 1;
                        break;
                    }
                    book[next_node] = 1;
                    queue[tail++] = next_node;
                    times[next_node]++;
                }
            }
            bian = next_road[bian];
        }
        book[queue[head]] = 0;
        head++;
        if(flag)
            break;
    }
    if(flag)
        cout << "存在负环";
    else
        for(int i=1; i<=n; i++)
            cout << dis[i] << ' ';
    cout << endl;
    return 0;
}

负环判断

Bellmam-Ford和SPFA算法都可以进行图的负环判断。
对于Bellman-Ford：第n次松弛操作还能成功更新dis[ ]的值，则存在负环
对于SPFA：如果一个点进入了队列n次，则存在负环

结论

算法	简述	时间复杂度	负权和负权回路
Floyd	动态规划	O(N^3)	可以处理负权,不能判断负权回路
Dijkstra	贪心,对点处理	O((M+N)logN)	什么都不能
Bellman-Ford	对边处理	O(MN)	可以处理负权,判断负权回路
SPFA	优化的Bellman	O(MN)	可以处理负权,判断负权回路

ㅤ

遇到的一些问题:

1. memset的原理

memset是为char[ ]设计，处理字节 , 即 memset(a,0xff,sizeof(a)) , 将a的每一个字节弄成 ff .
当我们对int[ ]使用memset时，int 4个字节每一个字节都会是 ff。
使用建议：

0x7f 每个字节第一位位0后面全是1，这是用memset让int能达到的最大值
0x3f 3f+3f=7e 达到无穷大+无穷大=无穷大的效果计算时避免溢出优于第一种

2. 生成随机数据

在C语言中，我们一般使用 <stdlib.h> 头文件中的 rand() 函数来生成随机数，它的用法为：int rand (void);
rand() 会随机生成一个位于 0 ~ RAND_MAX 之间的整数。
RAND_MAX 是 <stdlib.h> 头文件中的一个宏，它用来指明 rand() 所能返回的随机数的最大值。C语言标准并没有规定 RAND_MAX 的具体数值，只是规定它的值至少为 32767。在实际编程中，我们也不需要知道 RAND_MAX 的具体值，把它当做一个很大的数来对待即可。
srand((unsigned)time(NULL));重新播种

图论中几种最短路算法性能比较—— Floyd,Dijkstra,SPFA,Bellman-Ford及它们的优化

图论中几种最短路算法性能比较—— Floyd,Dijkstra,SPFA,Bellman-Ford及它们的优化

目录

Floyd

Dijkstra

Bellman-Ford 与 SPFA

比较结论

其他

1. Floyd

2. Dijkstra

邻接表