最短路汇总

DijkstraDijkstra的原理/流程?Dijkstra 本质上的思想是贪心它只适用于不含负权边的图。1. 初始化其余节点的值为无穷大。2. 找一个值最小的未操作过节点节点把节点标记。3. 遍历的所有出边若则令4. 重复 23 两步,直到所有点都操作。时间复杂度为。Dijkstra 为什么是正确的当所有边长都是非负数的时候,全局最小值不可能再被其他节点更新.所以在第2步中找出的蓝点x必然满足已经是起点到的最短路径.我们不断选择全局最小值进行标记和拓展,最终可以得到起点到每个节点的最短路径的长度。想要优化就直接维护最小值用优先队列即可。codevoid Dijkstra(int s,int t){ memset(dist,127,sizeof(dist)),dist[s]0,q.clear(); for(int i1;in;i) q.insert(make_pair(dist[i],i)); while(!q.empty()){ xq.begin()-second,q.erase(q.begin()); if(xt||dist[x]130) break; for(auto i:edge[x]) if(dist[x]i.vdist[i.y]) q.erase(make_pair(dist[i.y],i.y)),dist[i.y]dist[x]i.v,q.insert(make_pair(dist[i.y],i.y)); } }Bellman-Flord它的加速版就是 Dijkstra。想写出它上面多加几次循环不中途退出即可。Floyd你想像你是暴力人让后不停地更新所有更新了次用了。codefor(int k1;kn;k) for(int i1;in;i) for(int j1;jn;j) if(f[i][k]130f[k][j]130) f[i][j]min(f[i][j],f[i][k]f[k][j]);此算法要好好记虽然暴力但后面有大用。SPFA用数组记录源点到有向图上任意一点距离其中源点到自身距离为 0到其他点距离为无穷大。将源点入队并重复以下步骤队首出队。遍历所有以队首为起点的有向边若则更新。如果点不在队列中则入队。若队列为空跳出循环否则执行1。实际上我们可以将其理解为。codevoid spfa(){ q.push(A),dist[A]1,b[A]true; while(!q.empty()){ uq.front(),q.pop(),b[u]false; for(int it[u];i;iedge[i].y){ vedge[i].x; if(dist[v]dist[u]*edge[i].z){ dist[v]dist[u]*edge[i].z; if(!b[v]) q.push(v),b[v]true; } } } }//引入自 https://www.luogu.com.cn/problem/P1576JohnsonDijkstra 的升级版可以计算任意两个点之间的距离。新建一个虚拟 0 号节点。在节点 0 至节点中插入一条权值为 0 的有向边。使用 Bellman-ford 算法SPFA 也可计算节点 0 到其它节点的最短路径顺便判断负环记为​。将原图每条边的权值改为。跑轮 Dijkstra 算法求出全源最短路。代码就不贴了。搜索这是毫无疑问的详见A star寻路算法-CSDN博客后记妈呀太多了你只要记得 Dijkstra、Floyd 和 SPFA 就差不多了。要题目的话可以去 luogu 找找。广告有兴趣可以进 MYIOI 出题组哦要标明备注。MYIOI 出题组 - 洛谷