首页 > 代码库 > 最短路径(Dijkstra算法)
最短路径(Dijkstra算法)
当用图结构来表示通信、交通等网络,权重代表距离或者成本,寻找最短路径就成为了一个重要的任务。
给定带权网络G=(V;E),源点s,对于其他所有顶点v,寻找s到v的最短路径,连接成一颗最短路径树。可以证明,最短路径的任一前缀也是最短路径。
这一性质,可以理解为,对于一颗最短路径树,按到起点的距离排序,删除后面k个顶点以及关联边后,残存的子树T‘依然是最短路径树。因此,只需要找到一个新的距离源点s最近的顶点,即可扩充子树,最终成为全图的最短路径树。
考虑优先级搜索的框架,当前顶点尚未发现的邻接顶点,其优先级可以定义为其父亲的优先级加上联边的权重,即priority(u)=priority(parent(u))+weight(v,u)。与Prim算法类似,每次只需要将优先级最高的顶点以及联边加入子树,最终即可得到最短路径树。
1 template<typename Tv, typename Te> struct Dijkstra 2 { 3 virtual void operator()(Graph<Tv, Te>* g, int uk, int v) 4 { 5 if (g->status(v) == UNDISCOVERED)//对于uk每个尚未被发现的邻接顶点v 6 if (g->priority(v) > g->priority(uk) + g->weight(uk, v))//u到Vk的距离看做u的优先级 7 { 8 g->priority(v) = g->priority(uk) + g->weight(uk, v);//更新优先级数 9 g->parent(v) = uk;//更新父节点 10 } 11 }//每次都是寻找离开始节点s最近的节点,仅当新节点才更新,每个已发现节点的priority都是到s的最短距离 12 };
与Prim算法不同之处在于,Prim算法仅考虑子树到邻接顶点的联边权重;Dijkstra算法需要考虑的是到源点s的最短路径,基于前缀仍然是最短路径这一前提,只需要简化为,distance(s,u)=distance(s,v)+distance(v,u)。对应优先级,将边的权重作为优先级,即可实现。最后,沿着树边即可得到一颗最短路径树。
最短路径(Dijkstra算法)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。