DJ算法：
基本概念；
通过松弛每一个点（当前距离最小的点）的距离来达到最短距离。
不过不能解决有负权边的问题（会无线循环）。
时间复杂度；
O（n^2); （循环N次 每次在寻找N次的最小点 ，每次更新相邻点的时间忽略不计）
代码：
//vis【】检查是否到达过这个点，dis为到达每个点的距离 void djj(int s) { memset(dis,0x3f,sizeof dis); dis[s]=0;vis[s]=1; for(i=1;i<=n;i++) //循环N次，每次找出最短路 { for(int j==0;j<mzy[s].size();j++) //更新相邻的点 { if(dis[j]<mzy[s][j].w+dis[s]) { dis[j]==mzy[s][j].w+dis[s]; } } //寻找距离最短的点 int bestt=0x3f; for(int j==1;j<=n;j++) { if(bestt>dis[j]&&vis[j]==0) { bestt=dis[j];s=j; } } vis[s]==1; } }DJ的优化：
优先队列：
基本操作：
empty() 如果队列为空，则返回真
pop() 删除对顶元素，删除第一个元素
push() 加入一个元素
size() 返回优先队列中拥有的元素个数
top() 返回优先队列对顶元素，返回优先队列中有最高优先级的元素
在默认的优先队列中，优先级高的先出队。在默认的int型中先出队的为较大的数。
定义：
priority_queue <int,<vector>cmp> mqy;
cmp:
bool operator cmp(const int &a,int &b)const { return dis[a]>dis[b] //排序是反着来的，且排序的方式时按照return的方式。 }优化代码：
void djj(int s) { memset(dis,0x3f,sizeof dis); dis[s]=0;vis[s]=1; for(i=1;i<=n;i++) //循环N次，每次找出最短路 { for(int j==0;j<mzy[s].size();j++) //更新相邻的点 { if(dis[j]<mzy[s].w+dis[s]) { dis[j]==mzy[s].w+dis[s];mqy.push(j) } } while(!mqy.empty()&&vis[mqy.top()]==1) { mqy.pop(); } s=mqy.top(); //对优化点的处理 mqy.pop; vis[s]=1; } } DJ优化（优先队列）
spa算法：
优化板的暴力枚举，每个点最多进3次。
时间复杂度 O(E）；
代码：
spa void spa(int s) { int l,r,tremp; r++; while(l<r) { l++; tremp=que[l]; vis[tremp]=0; for(int j==0;j<mzy[tremp].size();j++) //更新相邻的点 { if(dis[mzy[tremp][j].v]<mzy[tremp].w+dis[tremp]) { dis[mzy[tremp][j].v]==mzy[tremp].w+dis[tremp]; if(vis[mzy[tremp][j].v]==0) r++,que[r]=mzy[tremp][j].v,vis[mzy[tremp][j].v]==1; } } if(r>3*n+1) break; //有环 } }Floyd算法
通过中间点更新两点间的距离。
用矩阵 arr 不能直接到达的点无穷大
代码
for(int k=0;k<n;k++)//k为中间节点 { for(int i=0;i<n;i++)//i为起点 for(int j=0;j<n;j++)//j为终点 if(i!=k&&i!=j&&k!=j) if(arr[i][k]+arr[k][j]<arr[i][j]) arr[i][j]=arr[i][k]+arr[k][j]; } Floyd
转载于:https://www.cnblogs.com/Lamboofhome/p/11375260.html
