最短路

n表示点的数量， m表示边的数量，当m和n^2 相近时是稠密图，当m和n相近时是稀疏图，用的是堆优化版的dijkstra算法

最短路算法的难点在建图

无向图是特殊的有向图，所以在最短路的算法当中，可以用有向图的算法来直接解决无向图的最短路问题

朴素dijkstra基本思路
定义一个int数组dist[]，表示每个点到原点的距离，定义一个bool数组st[],表示是否确定为最短路，初始化先让每个点的距离为正无穷，原点例如为1的距离为0，

memset(dist, 0x3f, sizeof dist);
dist[1] = 0

迭代 n 次表示遍历每一个点，之后每次迭代从1开始到n，让每一个还没有确定过最短距离，到达原点距离最小的点的距离确定，然后用它来更新其他点的距离，找这个点可以先定义一个中间变量 int t = -1;然后循环每次用if判断更新，如果t == -1 说明点还没找到让第一个点赋给t，之后每次比较disk[t]和disk[j]，如果后者比前者小则将更小的 j 赋值给 t ，最后当他跑完了之后留下来的那个点就是需要的点。

for (int j = 1; j <= n; j ++)
{
    dist[j] = min(disk[j], disk[t] + d[t][j]);
}

先是因为稠密图，所以用邻接矩阵来存，就是二维数组，d [N] [N].

例题：

Dijkstra求最短路I

给定一个 n个点 m条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出 1号点到 n号点的最短距离，如果无法从 1号点走到 n号点，则输出 −1。
输入格式
第一行包含整数 n和 m。
接下来 m行每行包含三个整数 x,y,z，表示存在一条从点 x到点 y的有向边，边长为 z。
输出格式
输出一个整数，表示 11 号点到 nn 号点的最短距离。
如果路径不存在，则输出 −1。
数据范围 1≤n≤500,1≤m≤1e5, 图中涉及边长均不超过10000。
输入样例：

输出样例：

思路：其中存在重边和自环，自环因为在更新距离的时候没有用到所以不用管，而重边，因为是求最短路，所以我们每次只要保存最短的一条就行，这就要求我门在一开始初始化d每条边的距离为无限大，之后每次存距离时用min函数更新，对于路径不存在的意思，就是一直到循环结束n号点的距离还是为0x3f3f3f3f,所以就是没有边可以将其连到原点，所以不存在，此时输出-1.

堆优化的dijkstra算法

优化在求每个没确定过的最短距离的点的步骤上，使用堆，可以手写也可以用优先队列，用优先队列可能会有数据的冗余，最后时间复杂度到mlogm，但是其等价于mlogn，（m近似于n^2,mlogm - > 2mlogn）.因为是稀疏表所以用邻接表来存，用邻接表来存的时候就不用关注重边，因为用到优先队列，虽然可能抽到两个一样的点，但是可以判断是否加过，加过了就跳过这个循环（用的是while循环，一直到最后没有新的点加入优先队列中，且原有的节点都遍历过了时循环结束，虽然有重复，但是重复的会continue，这和队列的循环判断一样，就是队列为空时循环结束），所以就不用在意（邻接矩阵在输入的时候要判断是因为他存不了重边）。需要注意的是和bfs求最短路的区别，就是他的权重不全为1，这意味着需要再来一个数组来存放权重，假设我们叫他w[].

例题：

Dijkstra求最短路II

给定一个 n个点 m条边的有向图，图中可能存在重边和自环，所有边权均为非负值。
请你求出 1号点到 n号点的最短距离，如果无法从 1号点走到 n号点，则输出 −1。
输入格式
第一行包含整数 n和 m。
接下来 m行每行包含三个整数x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1号点到 n号点的最短距离。
如果路径不存在，则输出−1。
数据范围 1≤n,m≤1.5×1e5, 图中涉及边长均不小于 0，且不超过10000。
数据保证：如果最短路存在，则最短路的长度不超过 1e9。
输入样例：

输出样例：

思路：定义一个小根堆

priority_queue<pair<int, int>, vector<pair<int, int> > , greater<pair<int, int> > > heap;

来维持还没确定的距离的点，因为这个点是要包含距离的，所以存的是pair，先将pair<int, int> {1,0} 存进去表示的是第一个点（原点）的距离为0，这是初始化，然后每次都将堆头取出，然后再弹出堆头，表示的是这个最小的已经确定了，之后在更新的时候只要判断某点原来的距离和这个点到那个点的距离的大小（不存在就是无穷大），然后如果比原来的小就加入到堆中。
后面就是一样的，当循环结束后判断是否有路径，有路径输出路径，没路径输出-1。

bellman_ford 算法基本思路
求权重为负的最短路问题。先是遍历n遍，每次遍历都遍历所有的边，然后更新所有的边。需要的数据结构只要是支持将边全部遍历就行，所以可以用结构体。
这样循环结束之后会使每一个点都会小于等于上一个点加上两点之间的权重。也叫做三角不等式

// 松弛操作
for (int i = 0; i < n; i ++)
{
    for (auto t : edges)
    {
        disk[b] = disk[a] + w
    }
}

//三角不等式
disk[b] <= disk[a] + w;

若图中存在负权回路，则有可能不存在最短路径，所以可以求出最短路的图一般情况下是不存在负权回路，负权回路就是一个环上的边权重总和是负的
松弛操作的n是有意义的，是说在不超过n条边的情况下最短路径，假设不是n是k就是在不超过k条边的最短路径。假如在第n次有更新，因为有n条边所以应该是n + 1个点，但是一共就是n个点，根据抽屉原理，可以知道两个点是一样的，所以就是成环了，因为有更新，所以值就是变小，所以就是负环。

例题：

有边数限制的最短路

给定一个 n个点 m条边的有向图，图中可能存在重边和自环，边权可能为负数。
请你求出从 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。
输入样例：

输出样例：

思路：为了避免串边所以需要新建一个数组backup[]，为了在更新的时候使用的上一次备份还没有操作过的点的距离。

memcpy(backup, disk, sizeof disk);

如果不备份的话假如k为1，就是不超过1条边，然后遍历所有的边，可能会出现3被更新成两条边的情况（如果这条边的出点被更新过）。因为可能有负环，所以最后在判断是否不存在的时候只要是路径长度大于一个很大的数就当作不存在，输出 -1 。（因为正无穷加上一个负数还是不存在，但是在判断的时候就不会等于我们设定的最大值）。

spfa算法思路
spfa有一个限制就是如果所要求最短路的图中有负环就不能用，但是一般情况下都没有。
spfa是以bellman_ford 算法为基础进行优化，优化的方向是更新的那部分，原因是当第一次更新之后如果下次再更新的时候如果a没有变小b也不会进行更新（每次都会把每一条边遍历一遍）。
所以我们新建一个队列，来保持一个变小的a，然后当这个队列不空的时候对b进行更新，之后将b加入到队列中变成了新的a，去更新其他边。这里有一个问题就是a可能会出现重复元素，因为每个元素都有可能有多个入度，所以为了避免这个情况在加入的时候要进行判断。这个其实就是基于bfs。数据结构可以使用邻接表
要记得在更新的时候是disk[j] > disk[t] + w 才更新，表示的是从上一个点走过来，比原来的路径要短，更新为最短路径。

例题：

spfa求最短路

给定一个 n个点 m条边的有向图，图中可能存在重边和自环，边权可能为负数。
请你求出 1号点到 n号点的最短距离，如果无法从 1号点走到 n号点，则输出 impossible。
数据保证不存在负权回路。
输入格式
第一行包含整数 n和 m。
接下来 m行每行包含三个整数x,y,z，表示存在一条从点 x到点 y的有向边，边长为 z。
输出格式
输出一个整数，表示 1号点到 n号点的最短距离。
如果路径不存在，则输出 impossible。
数据范围 1≤n,m≤1e5,
图中涉及边长绝对值均不超过10000。
输入样例：

输出样例：

spfa算法判断负环
和bellman_ford的思路一样只要边>=n，（可能不止有1一个点相等），就说明有负环。
所以我们可以新建一个数组cot[], 来维护每个点当前最短路径的边数，用到的等式是当前点的变数等于上个点的路径边数加1，当其上个点为原点时原点边数为0，其边数就为1 。
因为是判断图中有没有负环，并不是最短路径上有没有负环，所以如果负环没有在最短路径中就不会被查到，所以就是要在初始化的时候将每一个点都加入队列，让每一个点都为原点就不会漏环。

例题：

spfa判断负环

给定一个 n个点 m条边的有向图，图中可能存在重边和自环，边权可能为负数。
请你判断图中是否存在负权回路。
输入格式
第一行包含整数 n和 m。
接下来 m行每行包含三个整数 x,y,z，表示存在一条从点 x到点 y的有向边，边长为 z。
输出格式
如果图中存在负权回路，则输出 Yes，否则输出 No。
数据范围 1≤n≤2000 , 1≤m≤10000 , 图中涉及边长绝对值均不超过 10000。
输入样例：

输出样例：

Yes

Floyd算法求多源汇最短路
用到三重循环,用邻接矩阵来存所有的点，原理是基于动态规划。循环的时候必须先循环k，之后的i和j顺序可以颠倒，循环结束之后d从表示边权重的一个矩阵变成了每个点最短路径的一个矩阵，d[i] [j] 表示的就是从i到j的最短路径长度。floyd算法也可以求有负权的图，但是和spfa算法一样都是不能存在负环。

for （int k = 0; k < n; k ++)
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++)
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

例题：

Floyd求最短路

给定一个 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≤n，1≤m≤20000, 图中涉及边长绝对值均不超过10000。
输入样例：

输出样例：

impossible
1

思路：当判断不存在的时候和bellman_ford算法相似，因为有负权边的存在，最后正无穷可能不会是我们设置的最大值，所以只要让他大于某个很大的数就行，例如我们设置的值除以2.在初始化的时候由于不存在负环所以自环一定是正的，所以可以选择保留或者删去，保留的话就是在更新的时候因为不会变小所以没关系，当然要是删去也行。

//保留自环的初始化
memset(d, 0x3f, sizeof d);
//删去自环的初始化
const int INF = 1e9; //在下面判断的时候就是用 d[i][j] > IOF / 2 来判断是否存在
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;

Dijkstra求最短路I

Dijkstra求最短路II

有边数限制的最短路

spfa求最短路

spfa判断负环

Floyd求最短路

添加新评论

最新文章

最近回复

分类

归档

其它