马鞍山建设机械网站,国内ui做的好的网站有哪些,百度推广代理商加盟,永久免费云服务器推荐目录
Floyd算法
例题#xff1a;蓝桥公园
Dijkstra算法
例题#xff1a;蓝桥王国
SPFA算法
例题#xff1a;随机数据下的最短路问题
总结
最小生成树MST
Prim算法
Kruskal算法
例题#xff1a;聪明的猴子 Floyd算法
最简单的最短路径算法#xff0c;使用邻接…目录
Floyd算法
例题蓝桥公园
Dijkstra算法
例题蓝桥王国
SPFA算法
例题随机数据下的最短路问题
总结
最小生成树MST
Prim算法
Kruskal算法
例题聪明的猴子 Floyd算法
最简单的最短路径算法使用邻接矩阵存图因为Floyd算法计算的结果是所有点对之间的最短路本身就要的空间用矩阵存储最合适。效率不高计算复杂度为,只能用于n300的小规模的图不能用于大图在某些场景下有自己的优势难以替代能做传递闭包问题。
for(int k1;kn;k){for(int i1;in;i){for(int j1;jn;j){dp[i][j]min(dp[i][j],d[i][k]dp[k][j]);}}
}
Floyd算法是多源最短路算法以此计算能得到图中每一对结点之间多对多的最短路径。
Floyd算法能判断负圈若图中有权值为负的边某个经过这个负边的环路所有边长相加的总长度也是负数这就是负圈。在这个负圈上每绕一圈总长度就更小从而陷入在兜圈子的死循环。Floyd算法很容易判断负圈只要在算法运行过程中出现任意一个dp[i][j]0就说明有负圈因为dp[i][j]是从i出发经过其它中转点绕一圈回到自己的最短路径如果等于0就存在负圈。
例题蓝桥公园 #includebits/stdc.h
using namespace std;
const long long INF0x3f3f3f3f3f3f3f3fLL;
const int N405;
long long dp[N][N];
int n,m,q;
void floyd(){for(int k1;kn;k){for(int i1;in;i){for(int j1;jn;j){dp[i][j]min(dp[i][j],dp[i][k]dp[k][j]);}}}
}
int main(){cinnmq;memset(dp,0x3f,sizeof(dp));for(int i1;im;i){int u,v;long long w;cinuvw;dp[u][v]dp[v][u]min(dp[u][v],w);}floyd();while(q--){int s,t;cinst;if(dp[s][t]INF){cout-1endl;}else if(st){cout0endl;}else{coutdp[s][t]endl;}}return 0;
}
Dijkstra算法
Dijkstra算法用于求解单源最短路径问题非常高效而且稳定但是只能处理不含负权边的图。
Dijkstra算法是贪心思想实现的首先把起点到所有点的距离存下来找个最短的然后松弛一次再找出最短的所谓的松弛操作就是遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近如果更近了就更新距离这样把所有的点找遍之后就存下了起点到其它所有点的最短距离。
采用优先队列实现每次往队列中放数据时按从小到大的顺序放采用小顶堆的方式复杂度是保证最小的数总在最前面。找最小值直接取第一个数复杂度是。 例题蓝桥王国 #includebits/stdc.h
using namespace std;
const long long INF0x3f3f3f3f3f3f3f3fLL;
const int N3e52;
struct edge{int from,to;long long w;edge(int a,int b,long long c){froma;tob;wc;}
};
vectoredgee[N];
struct s_node{int id;long long n_dis;s_node(int b,long long c){idb;n_disc;}bool operator (const s_node a) const{ return n_disa.n_dis;}
};
int n,m;
int pre[N];
void print_path(int s,int t){if(st){printf(%d ,s);return;}print_path(s,pre[t]);printf(%d ,t);
}
long long dis[N];
void dijkstra(){int s1;bool done[N];for(int i1;in;i){dis[i]INF;done[i]false;}dis[s]0;priority_queues_nodeQ;Q.push(s_node(s,dis[s]));while(!Q.empty()){s_node uQ.top();Q.pop();if(done[u.id]){continue;}done[u.id]true;for(int i0;ie[u.id].size();i){edge ye[u.id][i];if(done[y.to]){continue;}if(dis[y.to]y.wu.n_dis){dis[y.to]y.wu.n_dis;Q.push(s_node(y.to,dis[y.to]));pre[y.to]u.id;}}}
}
int main(){cinnm;for(int i1;in;i){e[i].clear();}while(m--){int u,v,w;cinuvw;e[u].push_back(edge(u,v,w));}dijkstra();for(int i1;in;i){if(dis[i]INF){cout-1;}else{coutdis[i];}}return 0;
}
SPFA算法
SPFA算法队列处理Bellman-Ford
Bellman-Ford算法有很多低效或无效的操作其核心内容是在每一轮操作中更新所有节点到起点s的最短距离。
计算和调整一个节点u到s的最短距离后如果紧接着调整u的邻居节点这些邻居肯定有新的计算结果而如果漫无目的的计算不与u相邻的节点这可能毫无变化所以这些操作是低效的。
改进计算结点u之后下一步只计算和调整它的邻居能加速收敛的过程。这些步骤用队列操作 例题随机数据下的最短路问题 #includebits/stdc.h
using namespace std;
const long long INF0x3f3f3f3f3f3f3f3f;
const int N5e310;
struct edge{int to;long long w;edge(int tt,long long ww){tott;www;}
};
long long dist[N];
int inq[N];
vectoredgee[N];
void spfa(int s){memset(dist,0x3f,sizeof(dist));dist[s]0;queueintq;q.push(s);inq[s]1;while(!q.empty()){int uq.front();q.pop();inq[u]0;if(dist[u]INF){continue;}for(int i0;ie[u].size();i){int ve[u][i].to;long long we[u][i].w;if(dist[v]dist[u]w){dist[v]dist[u]w;if(!inq[v]){q.push(v);inq[v]1;}}}}
}
int main(){int n,m,s;cinnms;for(int i1;im;i){int u,v;long long w;cinuvw;e[u].push_back(edge(v,w));}spfa(s);for(int i1;in;i){if(dist[i]INF){cout-1;}else{coutdist[i];}if(i!n){cout ;}else{coutendl;}}return 0;
}
总结
单源最短路
1当权值非负时用Dijkstra算法。
2当权值有负值且没有负圈则用SPFA。SPFA能检测负圈但是不能输出负圈。
3当权值有负值而且有负圈需要输出则用Bellman-Ford能够检测并输出负圈。
多源最短路
使用Floyd算法。
最小生成树MST
一个含有n个结点的连通图的生成树是原图的极小连通子图包含原图中的所有n个结点并且边的权值之和最小。
Prim算法
对点进行贪心操作从任意一个点u开始把距离它最近的点加入到MST中下一步把距离{u,v}最近的点w加入到MST中继续这个过程直到所有的点都在MST中。适用于稠密图。
#includebits/stdc.h
using namespace std;
const int INF0x3f3f3f3f3f3f3f3f;
const int MAXN1005;
vectorintdemo;
int closest[MAXN],lowcost[MAXN],n,m;//m为节点的个数n为边的数量
int G[MAXN][MAXN];//邻接矩阵
int prim(){for(int i0;in;i){lowcost[i]INF;}for(int i0;im;i){closest[i]0;}closest[0]-1;//加入第一个点-1表示该点在集合U中否则在集合V中int num0,ans0,e0;while(numm-1){//当点还没有全部放进去 int micostINF;for(int i0;im;i){if(closest[i]!-1){int tempG[e][i];if(templowcost[i]){lowcost[i]temp;closest[i]e;}if(lowcost[i]micost){micostlowcost[i];}}ansmicost;demo.push_back(micost);closest[e]-1;num;}} return ans;
}
int main(){cinmn;memset(G,INF,sizeof(G));for(int i0;in;i){int a,b,c;cinabc;G[b][a]G[a][b]c;}coutprim()endl;for(int i0;im-1;i){coutdemo[i] ;}return 0;
}
Kruskal算法
对边进行贪心操作。从最短的边开始把它加入到MST中在剩下的边中找最短的边加入到 MST中继续这个过程直到所有的点都在MST中。适用于稀疏图。
kruskal算法的两个关键技术
1对边进行排序
2判断圈即处理连通性问题。这个问题用并查集简单而高效并查集是krustral算法的绝配。
例题聪明的猴子 #includebits/stdc.h
using namespace std;
int n,m,father[1100000];
struct node{int x,y,k;
}Q[1100000];
int find(int x){if(father[x]x){return x;}return father[x]find(father[x]);
}
bool cmp(node a,node b){return a.kb.k;
}
int main(){cinnm;int sum0,st0;for(int i0;im;i){//把m条边扫描进来 cinQ[i].xQ[i].yQ[i].k;}sort(Q,Qm,cmp);for(int i1;in;i){father[i]i;}for(int i0;im;i){int txfind(Q[i].x);int tyfind(Q[i].y);if(tx!ty){sumQ[i].k;st;father[tx]ty;if(stn-1){break;}}}coutsumendl;return 0;
}
