第三章 搜索与图论(二)

• 最短路
• • 朴素Dijkstra算法
  • 堆优化版的Dijkstra算法
  • Bellman-Ford算法
  • SPFA算法
  • • 求距离
    • 判负环
  • Floyd

并不区分有向图和无向图，因为无向图是一种特殊的有向图。直接用有向图的算法，解决无向图的问题。

常见情况可以分为两大类

在图论中，

源点就是起点，汇点就是终点

单源最短路：求一个点到其他所有点的最短距离

多源汇最短路：每个询问任选两个点，从一个点走到另一个点的最短路。起点与终点不确定

约定n表示图中点的数量，m表示边的数量

所有边权都是正数

朴素版算法时间复杂度与边数没有关系，比较适合于稠密图[边数比较多，边数与n²是一个级别的时候]

当n与m的级别相同时，不适合用朴素版算法，适合堆优化

存在负权边

虽然SPFA是Bellman算法优化，但不是所有情况都可以用SPFA算法

多源汇最短路

Floyd算法

总结

知识结构图

根据图的性质，选择不同的算法

最短路算法的侧重点与难点在于建图，如何把原问题抽象为最短路问题

不同的算法侧重点不同，最短路算法侧重于实现，其余算法可能侧重于原理

算法步骤：

s集合：当前已确定最短距离的点

1. 初始化距离，起点初始化为0，其他点初始化为正无穷

2. 循环迭代n次 1-n [每次迭代都可以确定一个点到起点的最短距离]

   1. 找到不在s中的距离最近的点t

   2. 将t加入到s中去

   3. 用t更新其他所有点的距离：

      1. 更新方式：从t出去所有点的边能不能更新距离

算法框架：

849. Dijkstra求最短路 I
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

输入格式
第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 −1。

数据范围
1≤n≤500,
1≤m≤105,
图中涉及边长均不超过10000。

输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3

举例：

1. 初始化

2. 迭代

   1. 第一次

      绿颜色表示已经确定的点，红颜色表示待定的点

   2. 第二次

   3. 第三次

时间复杂度：O(n²)

一个算法只有亲自实现，才叫做真正掌握

对于重边与自环需要有方式进行处理

#include 
#include 
#include 

using namespace std;
//n = 500,m = 100000,因此是稠密图，采用邻接矩阵
const int N = 510;
int n,m;
//邻接矩阵,g[a][b]表示节点a到节点b的链路的权重
int g[N][N];
//算法中距离，表示1号点走到每个点的当前的最短距离是多少
int dist[N];
//表示当前每个点的最短距离是否已经确定
bool st[N];

int dijkstra()
{
    //1. 初始化距离为无穷
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    //2. 迭代n次，每次寻找当前距离最小的点并添加至确定距离集合st中
    for(int i = 0;i < n;i++)
    {
        //从不确定的点中寻找最小的点，设定一个不存在的节点
        int t = -1;
        //遍历n个节点进行寻找没有确定并且距离最短的节点
        for(int j = 1;j <= n;j++)
            //条件：没有确定并且距离最短
            //如果j点没有确定 并且 t = -1或者j比当前距离要小
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        //t节点找到
        st[t] = true;
        //用1到t的长度加上t到j的长度更新1到j路径的长度
        for(int j = 1;j <= n;j++)
            dist[j] = min(dist[j],dist[t] + g[t][j]);
    }
    //如果距离认为无穷大，表明两点之间是不连通的
    if(dist[n] == 0x3f3f3f3f) return -1;
    //否则，返回最短距离
    return dist[n];
    
}

int main() 
{
    scanf("%d%d",&n,&m);
    //初始化：可以用memset，也可以用循环
    memset(g,0x3f,sizeof g);
        
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        //使用min：因为a b之间可能有多条边，只需要保留长度最短的那条边
        g[a][b] = min(g[a][b],c);
    }
    int t = dijkstra();
    cout< 
算法的关心的问题：能够在尽量短的时间内解决问题
 
工程关心问题：未来好维护
 
堆优化版的Dijkstra算法 
 
用堆来找距离最近的点O(1),堆修改一个数的复杂度O(logn),m次为O(mlogn)
 
用堆优化结束
 
 
堆的具体实现
 
C++提供的堆不支持修改数值,因此采用添加新数的方式，就扩大了堆的大小
 
 
logm与logn是一个级别的 ,mlogm与mlogn时间复杂度差不多。
 
一般不需要手写堆，直接使用C++中优先队列即可，只不过C++中可能有冗余
 
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

输入格式
第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 −1。

数据范围
1≤n,m≤1.5×105,
图中涉及边长均不小于 0，且不超过 10000。
数据保证：如果最短路存在，则最短路的长度不超过 109。

输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3
 
#include 
#include 
#include 
//需要用到优先队列
#include 
using namespace std;

//用堆维护所有点到源点的最短距离，维护距离时同时需要清楚节点编号
typedef pair PII;
const int N = 1000010;
int n,m;
//邻接表形式:需要存储一个权重w
int h[N],w[N],e[N],ne[N],idx;
//距离有两个变量在维护，一个是距离数组，一个是栈，栈的作用用于排序，找到距离最小的节点
//算法中距离，表示1号点走到每个点的当前的最短距离是多少
int dist[N];
//表示当前每个点的最短距离是否已经确定
bool st[N];
//节点a 节点b 节点a与节点b的距离c
void add(int a,int b,int c)
{
    e[idx] = b,w[idx] = c;ne[idx] = h[a],h[a] = idx++;
}

int dijkstra()
{
    //队列里面最多m个元素，因为有m条边
    //1. 初始化距离为无穷,节点1为0
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    //优先队列维护所有的距离
    //优先队列参数：vector代表用vector实现
    priority_queue,greater> heap;
    //一开始需要把一号点放入堆中，因为1号点已经知道最短距离
    //把一号点放进去更新所有点:距离是0，编号是1
    heap.push({0,1});
    while(heap.size())
    {
        //每次取出来距离最小的点
        auto t =heap.top();
        heap.pop();
        //ver表示编号 distance表示距离
        int ver = t.second,distance = t.first;
        //如果点已经出来过，说明当前点是冗余备份，就没有必要处理，直接continue
        if(st[ver]) continue;
        //更新状态
        st[ver] = true;
        //用当前点更新其余的点
        for(int i = h[ver];i != -1;i = ne[i] )
        {
            int j = e[i];
            //更新距离，distance表示ver节点到源点的最短距离，w[i]代表当前节点到e[i]节点的距离
            //如果成功
            if(dist[j] > distance + w[i])
            {
                //更新距离数组
                dist[j] = distance + w[i];
                //更新栈
                heap.push({dist[j],j});
            }
        }
    }
    
    
    //如果距离认为无穷大，表明两点之间是不连通的
    if(dist[n] == 0x3f3f3f3f) return -1;
    //否则，返回最短距离
    return dist[n];
    
}

int main() 
{
    scanf("%d%d",&n,&m);
    //初始化：邻接表开始有初始化的操作
    memset(h,-1,sizeof h);
    
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        //用邻接表，重边就无所谓了，最短路算法确保选择最短的边
        add(a,b,c);
    }
    int t = dijkstra();
    cout< 
 
 
学习的时候不能只停留在理解上，一定要多写多用
 
 
就和学习数学一样，明白一个定理是没有用的，一定要手算一下这个定理，增加熟练度，不然考试一定做不出来的。
 
 
写代码更是这样，更加重要，一定要多写
 
 
理解一个算法是没有任何意义的，因为你过两天就忘了，一定要写出来
 
 
比如学自行车、学游泳，学会之后几年都不会忘，背个单词，吃完饭可能就忘了
 
 
理解之后很容易忘记，写一遍之后类似学自行车，动作记忆，很难忘
 
 
一定要多写
 
 
可以发现，学习不一定是脑力活，很可能是体力活
 
 
Bellman-Ford算法 
迭代n次，每一次循环所有边。
 
a,b,w表示存在由a指向b权重为w的边。
 
存储方式不一定用临接表，可以用最傻瓜的方式，比如开一个结构体
 
更新所有距离
 
 
时间复杂度：
 
第一层循环n；第二层循环m 时间复杂度O(nm)
 
完成以上步骤，一定有
 
 
如果由负权回路[回路整体一圈的权重小于0]的话，最短路是不一定存在的，比如1->5
 
 
迭代次数的含义：
 
迭代k次：从1号点经过不超过K条边的最短路的距离
 
迭代n次时有更新时：
 
n+1个点->仍有更新->存在负环
 
有边数限制的最短路
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。//不能用Dijkstra

//限制了最短路的边的个数，有负环就无所谓了
请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。

注意：图中可能 存在负权回路 。

输入格式
第一行包含三个整数 n,m,k。

接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

点的编号为 1∼n。

输出格式
输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。

如果不存在满足条件的路径，则输出 impossible。

数据范围
1≤n,k≤500,
1≤m≤10000,
1≤x,y≤n，
任意边长的绝对值不超过 10000。

输入样例：
3 3 1
1 2 1
2 3 1
1 3 3
输出样例：
3
 
迭代的时候需要备份，不加备份，可能发生串联。枚举一次，可能更新多个点到源点的距离。
 
保证不发生串联：只用上一次迭代的结果
 
 
 
边数有限制，只能有一条边
 
#include 
#include 
#include 

using namespace std;

const int N = 510,M = 10010;

int n,m,k;

int dist[N],backup[N];
struct Edge
{
    int a,b,w;
}edges[M];

void bellman_ford()
{
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    for(int i = 0;i < k;i++)
    {
        memcpy(backup,dist,sizeof dist);
        for(int j = 0;j 
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            //只用上一次更新的数据更新，避免产生串联
            dist[b] = min(dist[b],backup[a] + w);
        }
    }

}



int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i = 0;i < m;i++)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        edges[i] = {a,b,w}; 
    }
    bellman_ford();
 //存在负权边，将N点距离更新，但是减去的范围也不会太大
    if(dist[n] > 0x3f3f3f3f/2) puts("impossible");
    else printf("%dn",dist[n]);
    
    return 0;
    
}
 
SPFA算法 
求距离 
B-L每次迭代遍历所有边更新，但每次不一定都能使得变小
 
 
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。

数据保证不存在负权回路。

输入格式
第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 impossible。

数据范围
1≤n,m≤105,
图中涉及边长绝对值均不超过 10000。

输入样例：
3 3
1 2 5
2 3 -3
1 3 4
输出样例：
2
 
#include 
#include 
#include 
//需要用到优先队列
#include 
using namespace std;

//用堆维护所有点到源点的最短距离，维护距离时同时需要清楚节点编号
typedef pair PII;
const int N = 1000010;
int n,m;
//邻接表形式:需要存储一个权重w
int h[N],w[N],e[N],ne[N],idx;
//距离有两个变量在维护，一个是距离数组，一个是栈，栈的作用用于排序，找到距离最小的节点
//算法中距离，表示1号点走到每个点的当前的最短距离是多少
int dist[N];

bool st[N];
//节点a 节点b 节点a与节点b的距离c
void add(int a,int b,int c)
{
    e[idx] = b,w[idx] = c;ne[idx] = h[a],h[a] = idx++;
}

void spfa()
{
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    
    queue q;
    q.push(1);
    //st数组存储点是否在队列中，防止队列中存储重复的点
    st[1] = true;
    
    while(q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        for(int i = h[t];i != -1;i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if(!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
        
    }
    if(dist[n] == 0x3f3f3f3f) puts("impossible");
    else printf("%dn",dist[n]);
    
    
}

int main() 
{
    scanf("%d%d",&n,&m);
    //初始化：邻接表开始有初始化的操作
    memset(h,-1,sizeof h);
    
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        //用邻接表，重边就无所谓了，最短路算法确保选择最短的边
        add(a,b,c);
    }
    spfa();

    
    return 0;
}
 
判负环 
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你判断图中是否存在负权回路。

输入格式
第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式
如果图中存在负权回路，则输出 Yes，否则输出 No。

数据范围
1≤n≤2000,
1≤m≤10000,
图中涉及边长绝对值均不超过 10000。

输入样例：
3 3
1 2 -1
2 3 4
3 1 -4
输出样例：
Yes
 
 
 
#include 
#include 
#include 
//需要用到优先队列
#include 
using namespace std;

//用堆维护所有点到源点的最短距离，维护距离时同时需要清楚节点编号
typedef pair PII;
const int N = 1000010;
int n,m;
//邻接表形式:需要存储一个权重w
int h[N],w[N],e[N],ne[N],idx;
//距离有两个变量在维护，一个是距离数组，一个是栈，栈的作用用于排序，找到距离最小的节点
//算法中距离，表示1号点走到每个点的当前的最短距离是多少
int dist[N],cnt[N];
//表示当前每个点的最短距离是否已经确定
bool st[N];
//节点a 节点b 节点a与节点b的距离c
void add(int a,int b,int c)
{
    e[idx] = b,w[idx] = c;ne[idx] = h[a],h[a] = idx++;
}

bool spfa()
{
    queue q;
    //将所有点放到队列中，因为不是从1号点开始寻找
    for(int i = 1;i <=n;i++)
    {
        st[i] = true;
        q.push(i);
    }
    
    while(q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        for(int i = h[t];i != -1;i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                
                if(cnt[j] >= n) return true;
                if(!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
        
    }
    return false;
}

int main() 
{
    scanf("%d%d",&n,&m);
    //初始化：邻接表开始有初始化的操作
    memset(h,-1,sizeof h);
    
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        //用邻接表，重边就无所谓了，最短路算法确保选择最短的边
        add(a,b,c);
    }
    if(spfa()) puts("Yes");
    else puts("No");

    
    return 0;
}
 
Floyd 
邻接矩阵存储所有点之间的边
 
三层循环
 
K： 1-n
 
I: 1-n
 
j: 1-N
 
 
循环后d[i][j]存储最短路的长度
 
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。

再给定 k 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，则输出 impossible。

数据保证图中不存在负权回路。

输入格式
第一行包含三个整数 n,m,k。

接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

接下来 k 行，每行包含两个整数 x,y，表示询问点 x 到点 y 的最短距离。

输出格式
共 k 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出 impossible。

数据范围
1≤n≤200,
1≤k≤n2
1≤m≤20000,
图中涉及边长绝对值均不超过 10000。

输入样例：
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
输出样例：
impossible
1
 
#include 
#include 
#include 

using namespace std;

const int N = 210,INF = 1e9;

int n,m,Q;
int d[N][N];


void floyd()
{
    for(int k = 1; k <= n;k++)
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= n;j++)
                d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
}

int main()
{
    scanf("%d%d%d",&n,&m,&Q);
    for(int i = 1; i<=n;i++)
        for(int j = 1;j <=n;j++)
            if(i == j) d[i][j] =0;
            else d[i][j] = INF;
    while(m--)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        d[a][b] = min(d[a][b],w);
    }
    floyd();
    while(Q--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(d[a][b] > INF/2) puts("impossible");
        else printf("%dn",d[a][b]);
    }
    return 0;
}
 
调代码：
 
printf
注释代码