首页 > 代码库 > 最短路径(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算法)