图论详解 |
您所在的位置：网站首页 › 图论中的完全树是指 › 图论详解 |
图论详解
|
在学习dijkstra之前，如果你没学过Bellman-ford算法的话，dijkstra确实会很难懂 Bellman-ford详解 一.原理 思想ford算法是利用动态规划的思想，而dijkstra是运用贪心策略，找到原点的最短路径 演示dijkstra利用蓝白点的思想 蓝点代表还未访问，白点代表已经更新 原点：1 目标点：5 
初始化原点最短路径为0 
找到离原点最近的点，也就是2号点，所以更新它 
2最近的是1，但4大于0，所以更新不了 更新3号点 
更新四号节点 
最后更新5号节点 
整个过程结束 所以最短路径就是16 dijkstra的运行过程就是这样 二.代码详解其他地方没什么区别 这一块是主要思想 void dijkstra(){ memset(f,0x7f,sizeof(f)); memset(vis,0,sizeof(vis));//状态 f[s]=0; while(flag){ flag=0; int now=0; for (int i=1;if[i]){//寻找最短路径最短的 flag=1; now=i; } } } vis[now]=1; for (int k=adj[now];k;k=e[k].nxt){//遍历，更新 int l=e[k].to; if (!vis[l]){ relax(now,l,e[k].w); } } } }好处：他的时间空间复杂度都没问题，但可以使用优先队列优化一下 缺点：难懂，不能处理负权环 例题： 平面上有n个点（n≤100），每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。 若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。 输入 共n+m+3行，其中: 第一行为整数n。 第2行到第n+1行（共n行） ，每行两个整数x和y，描述了一个点的坐标。 第n+2行为一个整数m(mf[u]+w){ f[v]=f[u]+w; } } void dijkstra(){ memset(f,0x7f,sizeof(f)); memset(vis,0,sizeof(vis)); f[s]=0; while(flag){ flag=0; int now=0; for (int i=1;if[i]){ flag=1; now=i; } } } vis[now]=1; for (int k=adj[now];k;k=e[k].nxt){ int l=e[k].to; if (!vis[l]){ relax(now,l,e[k].w); } } } } signed main(){ scanf("%lld",&n); for (int i=1;i |
【本文地址】
今日新闻 |
推荐新闻 |