个人域名备案网站内容怎么写,三丰云免费服务器,百度推广引流多少钱一个月,郑州门户网站建设spfa算法是对bellman_ford算法的优化#xff0c;大部分求最短路问题都可以用spaf算法来求。
注意#xff1a;
#xff08;1#xff09;如若图中有负权回路#xff0c;不能用spfa算法#xff0c;要用bellman_ford算法#xff1b;若只有负权边#xff0c;则可以用
spf…spfa算法是对bellman_ford算法的优化大部分求最短路问题都可以用spaf算法来求。
注意
1如若图中有负权回路不能用spfa算法要用bellman_ford算法若只有负权边则可以用
spfa算法
2Dijikstra算法适用于图中全都是正权边
spfa算法
step1:
初始化
step2
取出队头结点弹出队头遍历队头结点的子结点更新距离
step3
如若第一次更新距离(st[j] false)将结点编号加入队列。
step4
重复循环直至队列没有结点编号说明到头了。 题目如下
给定一个 n 个点 m 条边的有向图图中可能存在重边和自环 边权可能为负数。
请你求出 1 号点到 n 号点的最短距离如果无法从 1 号点走到 n 号点则输出 impossible。
数据保证不存在负权回路。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边边长为 z。
输出格式
输出一个整数表示 1 号点到 n 号点的最短距离。
如果路径不存在则输出 impossible。
数据范围
1≤n,m≤105, 图中涉及边长绝对值均不超过 10000。 解答代码如下
//主要解决三个问题
//1st数组有啥用:if(st[j] true)//提高速度//处理重边
//2用spfa时为啥图中不能有负权回路模拟一遍就会了因为while(q.size())
//3为什么要用队列
#includeiostream
#includecstring
#includequeueusing namespace std;const int N 100010;int n,m;
int e[N],ne[N],h[N],idx,w[N];
int dist[N];
bool st[N];//如st[i]记录的是编号i结点是否是在队列中void add(int a,int b,int c)
{e[idx] b;w[idx] c;ne[idx] h[a];h[a] idx;idx;
}int spfa()
{memset(dist,0x3f,sizeof(dist));dist[1] 0;queueint q;q.push(1);//队列q中存储的是上一次循环中被更新最短路径的结点编号st[1] true;//st数组中存储的是此时编号 i 结点是否在队列中while(q.size()){int t q.front();q.pop();//q中只存储上一次循环中被确定最短路径长的结点的编号再上一次的会被弹出st[t] false;for (int i h[t];i ! -1;i ne[i]){int j e[i];if (dist[j] dist[t] w[i])//通过if语句判定说明编号 j 结点需要更新{dist[j] dist[t] w[i];if (!st[j])//判断q会不会出现重复的结点{q.push(j);//如果这个结点的距离是第一次被更新初始值都是0x3f3f3f3f//那么就进入队列在下一次循环中q队列中存储的就是上一次循环//更新路径长度的结点编号了st[j] true;//标记编号 j 结点}}}}return dist[n];}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin n m;memset(h,-1,sizeof(h));while(m--){int a,b,c;cin a b c;add(a,b,c);}int t spfa();if (t 0x3f3f3f3f)cout impossible;elsecout t;return 0;
} 模拟过程 1 为什么用队列
spfa算法中使用队列是为了优化bellman_ford算法中的遍历每一条边来找到编号 t 结点的子结点
使用队列后如此时t 1那么这一次循环中更新了 dist 第一次走到某结点时都会更新因为第一次走到某结点时的 dist 都是 0x3f3f3f3f 的结点就是编号 1 结点的子结点加更新了 dist加入到队列下次循环时直接取出就可以省略遍历所有边
2为什么不能有负权回路 3st数组有什么用
我认为的作用之一就是处理重边
