温州专业营销网站建设,网络建设解决方案,设计网站需要哪些流程,上海市建设人才网站文章目录最短路朴素Dijkstra算法堆优化版的Dijkstra算法Bellman-Ford算法SPFA算法求距离判负环Floyd最短路
并不区分有向图和无向图#xff0c;因为无向图是一种特殊的有向图。直接用有向图的算法#xff0c;解决无向图的问题。
常见情况可以分为两大类 在图论中#xff0…
文章目录最短路朴素Dijkstra算法堆优化版的Dijkstra算法Bellman-Ford算法SPFA算法求距离判负环Floyd最短路
并不区分有向图和无向图因为无向图是一种特殊的有向图。直接用有向图的算法解决无向图的问题。
常见情况可以分为两大类 在图论中
源点就是起点汇点就是终点
单源最短路求一个点到其他所有点的最短距离
多源汇最短路每个询问任选两个点从一个点走到另一个点的最短路。起点与终点不确定
约定n表示图中点的数量m表示边的数量
所有边权都是正数
朴素版算法时间复杂度与边数没有关系比较适合于稠密图[边数比较多边数与n2是一个级别的时候]
当n与m的级别相同时不适合用朴素版算法适合堆优化
图区别存储稠密图m~n2邻接矩阵稀疏图m~n邻接表存在负权边
虽然SPFA是Bellman算法优化但不是所有情况都可以用SPFA算法 多源汇最短路
Floyd算法
总结
知识结构图 根据图的性质选择不同的算法
最短路算法的侧重点与难点在于建图如何把原问题抽象为最短路问题
不同的算法侧重点不同最短路算法侧重于实现其余算法可能侧重于原理
朴素Dijkstra算法
算法步骤
s集合当前已确定最短距离的点 初始化距离起点初始化为0其他点初始化为正无穷 循环迭代n次 1-n [每次迭代都可以确定一个点到起点的最短距离] 找到不在s中的距离最近的点t 将t加入到s中去 用t更新其他所有点的距离 更新方式从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举例
初始化 迭代 第一次 绿颜色表示已经确定的点红颜色表示待定的点 第二次 第三次
时间复杂度O(n2)
一个算法只有亲自实现才叫做真正掌握
对于重边与自环需要有方式进行处理
#include iostream
#include cstring
#include algorithmusing 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);/*for(int i 1;i n;i)for(int j 1;j n;j)if(i j) g[i][j] 0;else g[i][j] INF;*/ 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();couttendl;return 0;
}算法的关心的问题能够在尽量短的时间内解决问题
工程关心问题未来好维护
堆优化版的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 iostream
#include cstring
#include algorithm
//需要用到优先队列
#include queue
using namespace std;//用堆维护所有点到源点的最短距离维护距离时同时需要清楚节点编号
typedef pairint,int 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为0memset(dist,0x3f,sizeof dist);dist[1] 0;//优先队列维护所有的距离//优先队列参数vector代表用vector实现priority_queuePII,vectorPII,greaterPII heap;//一开始需要把一号点放入堆中因为1号点已经知道最短距离//把一号点放进去更新所有点:距离是0编号是1heap.push({0,1});while(heap.size()){//每次取出来距离最小的点auto t heap.top();heap.pop();//ver表示编号 distance表示距离int ver t.second,distance t.first;//如果点已经出来过说明当前点是冗余备份就没有必要处理直接continueif(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();couttendl;return 0;
}学习的时候不能只停留在理解上一定要多写多用 就和学习数学一样明白一个定理是没有用的一定要手算一下这个定理增加熟练度不然考试一定做不出来的。 写代码更是这样更加重要一定要多写 理解一个算法是没有任何意义的因为你过两天就忘了一定要写出来 比如学自行车、学游泳学会之后几年都不会忘背个单词吃完饭可能就忘了 理解之后很容易忘记写一遍之后类似学自行车动作记忆很难忘 一定要多写 可以发现学习不一定是脑力活很可能是体力活 Bellman-Ford算法
迭代n次每一次循环所有边。
a,b,w表示存在由a指向b权重为w的边。
存储方式不一定用临接表可以用最傻瓜的方式比如开一个结构体
更新所有距离 时间复杂度
第一层循环n第二层循环m 时间复杂度O(nm)
完成以上步骤一定有 如果由负权回路[回路整体一圈的权重小于0]的话最短路是不一定存在的比如1-5 迭代次数的含义
迭代k次从1号点经过不超过K条边的最短路的距离
迭代n次时有更新时
n1个点-仍有更新-存在负环
有边数限制的最短路
给定一个 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 cstring
#include iostream
#include algorithmusing 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 m;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(%d\n,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 iostream
#include cstring
#include algorithm
//需要用到优先队列
#include queue
using namespace std;//用堆维护所有点到源点的最短距离维护距离时同时需要清楚节点编号
typedef pairint,int 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;queueint 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(%d\n,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 iostream
#include cstring
#include algorithm
//需要用到优先队列
#include queue
using namespace std;//用堆维护所有点到源点的最短距离维护距离时同时需要清楚节点编号
typedef pairint,int 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()
{queueint 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 iostream
#include string
#include algorithmusing 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; in;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(%d\n,d[a][b]);}return 0;
}调代码
printf注释代码
