企业官网建设流程全解析

Dijkstra

Dijkstra的原理/流程?

Dijkstra 本质上的思想是贪心，它只适用于不含负权边的图。

1. 初始化，其余节点的值为无穷大。

2. 找一个值最小的未操作过节点节点，把节点标记。

3. 遍历的所有出边，若，则令

4. 重复 2，3 两步,直到所有点都操作。

时间复杂度为。

Dijkstra 为什么是正确的

当所有边长都是非负数的时候,全局最小值不可能再被其他节点更新.所以在第2步中找出的蓝点x必然满足：

已经是起点到的最短路径.我们不断选择全局最小值进行标记和拓展,最终可以得到起点到每个节点的最短路径的长度。

想要优化就直接维护最小值用优先队列即可。

code：

void Dijkstra(int s,int t){ memset(dist,127,sizeof(dist)),dist[s]=0,q.clear(); for(int i=1;i<=n;i++) q.insert(make_pair(dist[i],i)); while(!q.empty()){ x=q.begin()->second,q.erase(q.begin()); if(x==t||dist[x]>1<<30) break; for(auto i:edge[x]) if(dist[x]+i.v<dist[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

你想像你是暴力人，让后不停地更新所有，更新了次，用了。

code：

for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(f[i][k]<1<<30&&f[k][j]<1<<30) f[i][j]=min(f[i][j],f[i][k]+f[k][j]);

此算法要好好记，虽然暴力但后面有大用。

SPFA

用数组记录源点到有向图上任意一点距离，其中源点到自身距离为 0，到其他点距离为无穷大。将源点入队，并重复以下步骤：

1. 队首出队。

2. 遍历所有以队首为起点的有向边，若，则更新。

3. 如果点不在队列中，则入队。

4. 若队列为空，跳出循环，否则执行1。

实际上我们可以将其理解为。

code：

void spfa(){ q.push(A),dist[A]=1,b[A]=true; while(!q.empty()){ u=q.front(),q.pop(),b[u]=false; for(int i=t[u];i;i=edge[i].y){ v=edge[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/P1576

Johnson

Dijkstra 的升级版，可以计算任意两个点之间的距离。

1. 新建一个虚拟 0 号节点。

2. 在节点 0 至节点中插入一条权值为 0 的有向边。

3. 使用 Bellman-ford 算法（SPFA 也可）计算节点 0 到其它节点的最短路径（顺便判断负环），记为​。

4. 将原图每条边的权值改为。

5. 跑轮 Dijkstra 算法，求出全源最短路。

代码就不贴了。

搜索

这是毫无疑问的，详见：

A star寻路算法-CSDN博客

后记

妈呀！太多了！

你只要记得 Dijkstra、Floyd 和 SPFA 就差不多了。

要题目的话可以去 luogu 找找。

广告

有兴趣可以进 MYIOI 出题组哦，要标明备注。

MYIOI 出题组 - 洛谷