微投票网站,win7优化教程,网站关联页面如何做,网址seo关键词⭐️dijkstra
介绍#xff08;想看的可以看#xff09;
Dijkstra算法#xff08; /ˈdaɪkstrəz/ DYKE-str z#xff09;是一种用于找到加权图中的节点之间的最短路径的算法#xff0c;该加权图可以表示例如道路网络。它是由计算机科学家Edsger W. Dijkstra于1956年出版…⭐️dijkstra
介绍想看的可以看
Dijkstra算法 /ˈdaɪkstrəz/ DYKE-str z是一种用于找到加权图中的节点之间的最短路径的算法该加权图可以表示例如道路网络。它是由计算机科学家Edsger W. Dijkstra于1956年出版三年后出版。 该算法存在许多变体。Dijkstra的原始算法找到了两个给定节点之间的最短路径但更常见的变体将单个节点固定为“源”节点并找到从源到图中所有其他节点的最短路径生成最短路径树。 对于图中给定的源节点该算法找到该节点与其他节点之间的最短路径。 它也可以用于找到从单个节点到单个目的地节点的最短路径一旦到目的地节点的最短路径已经确定就停止算法。例如如果图中的节点表示城市而边路径的成本表示通过直接道路连接的成对城市之间的驾驶距离为简单起见忽略红灯停车标志收费公路和其他障碍物则Dijkstra算法可以用于找到一个城市和所有其他城市之间的最短路线。最短路径算法的一个广泛应用是网络路由协议最著名的是IS-IS中间系统到中间系统和OSPF开放最短路径优先。它也被用作其他算法如约翰逊算法的子程序。 Dijkstra算法使用的标签是正整数或真实的数字它们是完全有序的。它可以推广到使用任何部分有序的标签只要后续标签遍历边时产生后续标签是单调非递减的。这种推广称为通用Dijkstra最短路径算法。 Dijkstra的算法使用一种数据结构来存储和查询从一开始就按距离排序的部分解。Dijkstra的原始算法不使用最小优先级队列并在时间 。该算法的思想也在Leyzorek et al. 1957中给出。Fredman Tarjan 1984提出使用Fibonacci堆最小优先级队列来优化运行时间复杂度到 。这是渐近已知的最快的单源最短路径算法任意有向图与无界非负权重。然而特殊情况如有界/整数权重有向无环图等确实可以进一步改进如专业化变体中所述。此外如果允许预处理诸如收缩层次结构之类的算法可以快七个数量级。 在许多领域特别是人工智能领域Dijkstra算法或其变体被称为均匀成本搜索并被公式化为更一般的最佳优先搜索思想的实例. 另外的两个最短路算法 bellman-ford算法 floyd算法 具体原理
在图中所有的边上排满多米诺骨牌相当于把骨牌看成图的边。一条边上的多米诺骨牌数量和边的权值例如长度或费用成正比。规定所有骨牌倒下的速度都是一样的。如果在一个结点上推倒骨牌会导致这个结点上的所有骨牌都往后面倒下去。 在起点s推倒骨牌可以观察到从s开始它连接的边上的骨牌都逐渐倒下并到达所有能达到的结点。在某个结点t可能先后从不同的线路倒骨牌过来先倒过来的骨牌其经过的路径肯定就是从s到达t的最短路后倒过来的骨牌对确定结点t的最短路没有贡献不用管它。 从整体看这就是一个从起点s扩散到整个图的过程。 在这个过程中观察所有结点的最短路径是这样得到的 1在s的所有直连邻居中最近的邻居u骨牌首先到达。u是第一个确定最短路径的结点。从u直连到s的路径肯定是最短的因为如果u绕道别的结点到s必然更远。 2然后把后面骨牌的倒下分成2部分一部分是从s继续倒下到s的其它的直连邻居另一部分从u出发倒下到u的直连邻居。那么下一个到达的结点v必然是s或者u的一个直连邻居。v是第二个确定最短路径的结点。 3继续以上步骤在每一次迭代过程中都能确定一个结点的最短路径。 Dijkstra算法应用了贪心法的思想即“抄近路走肯定能找到最短路径”。算法可以简单概况为Dijkstra BFS 贪心。实际上“Dijkstra 优先队列 BFS 优先队列队列中的数据是从起点到当前点的距离”。 下面分析复杂度。设图的点有n个边有m条。编码的时候集合A一般用优先队列来模拟。优先队列可以用堆或其他高效的数据结构实现往优先队列中插入一个数、取出最小值的操作都是O(logn)的。一共往队列中插入m次每条边都要进集合A一次取出n次每次从集合A中取出距离s最短的一个点取出时要更新这个点的所有邻居到s的距离设一个点平均有k个邻居那么总复杂度是O(m×logn n×k×logn) O(m×logn)一般有m大于n。 模板题
问题描述
蓝桥王国一共有N个建筑和M条单向道路每条道路都连接着两个建筑每个建筑都有自己编号分别为1∼。其中皇宫的编号为1国王想让小明回答从皇宫到每个建筑的最短路径是多少但紧张的小明此时已经无法思考请你编写程序帮助小明回答国王的考核。 格式输入
输入第一行包含2个正整数N,M。第2到M1行每行包含三个正整数u,v,w表示u→v之间存在一条距离为w的路。1≤N≤3×1051≤m≤1061≤ui ,vi≤N0≤wi≤109。 格式输出
输出仅一行共N个数分别表示从皇宫到编号为1∼N建筑的最短距离两两之间用空格隔开。如果无法到达则输出−1 样例输入
3 3 1 2 1 1 3 5 2 3 2 样例输出
0 1 3 解析
dijkstra求解 参考程序
#includebits/stdc.h
//#define inf LONG_MAX
using namespace std;
const long long inf0x3f3f3f3f3f3f3f3fLL;
const int N3e52;
int n,m,u,v;
long long dis[N],w;
struct edg{int to;long long d;
};
vectoredg g[N];
struct node{int id;long long dis;bool operator (const node a)const{return disa.dis;}node(int b,long long c){idb;disc;}
};
void dijkstra()
{//node node1(1,0);dis[1]0;priority_queue node q;q.push(node(1,0));int done[N];for (int i1;in;i)done[i]0;while(!q.empty()){node node1q.top();q.pop();int id1node1.id;if(done[id1]) continue;done[id1]1;int szg[id1].size();for (int i0;isz;i){if(done[g[id1][i].to]) continue;if(dis[g[id1][i].to]node1.disg[id1][i].d)dis[g[id1][i].to]node1.disg[id1][i].d;q.push(node(g[id1][i].to,dis[g[id1][i].to]));}}}
int main()
{cinnm;for (int i1;in;i)dis[i]inf;for (int i1;im;i){cinuvw;g[u].push_back({v,w});//g[v].push_back({u,w});}dijkstra();for (int i1;in;i){if(dis[i]inf)cout-1 ;elsecoutdis[i] ;} return 0;}以个人刷题整理为目的如若侵权请联系删除~
