最短路径(Dijkstra算法)
2024-08-30 05:32:21
当用图结构来表示通信、交通等网络,权重代表距离或者成本,寻找最短路径就成为了一个重要的任务。
给定带权网络G=(V;E),源点s,对于其他所有顶点v,寻找s到v的最短路径,连接成一颗最短路径树。可以证明,最短路径的任一前缀也是最短路径。
这一性质,可以理解为,对于一颗最短路径树,按到起点的距离排序,删除后面k个顶点以及关联边后,残存的子树T‘依然是最短路径树。因此,只需要找到一个新的距离源点s最近的顶点,即可扩充子树,最终成为全图的最短路径树。
考虑优先级搜索的框架,当前顶点尚未发现的邻接顶点,其优先级可以定义为其父亲的优先级加上联边的权重,即priority(u)=priority(parent(u))+weight(v,u)。与Prim算法类似,每次只需要将优先级最高的顶点以及联边加入子树,最终即可得到最短路径树。
template<typename Tv, typename Te> struct Dijkstra
{
virtual void operator()(Graph<Tv, Te>* g, int uk, int v)
{
if (g->status(v) == UNDISCOVERED)//对于uk每个尚未被发现的邻接顶点v
if (g->priority(v) > g->priority(uk) + g->weight(uk, v))//u到Vk的距离看做u的优先级
{
g->priority(v) = g->priority(uk) + g->weight(uk, v);//更新优先级数
g->parent(v) = uk;//更新父节点
}
}//每次都是寻找离开始节点s最近的节点,仅当新节点才更新,每个已发现节点的priority都是到s的最短距离
};
与Prim算法不同之处在于,Prim算法仅考虑子树到邻接顶点的联边权重;Dijkstra算法需要考虑的是到源点s的最短路径,基于前缀仍然是最短路径这一前提,只需要简化为,distance(s,u)=distance(s,v)+distance(v,u)。对应优先级,将边的权重作为优先级,即可实现。最后,沿着树边即可得到一颗最短路径树。
最新文章
- TDD学习笔记【四】--- 如何隔离相依性 - 基本的可测试性
- Cannot attach the file ‘{0}&#39; as database &#39;{1}&#39;
- httpd安装.md
- MySQL中VARCHAR与CHAR格式数据的区别
- 我是如何使用git的
- 中文在unicode中的编码范围
- Linux权限值问题
- 杨辉三角 &;&; 鸽兔同校
- Node与Express开发 坑1
- iOS开发——UI篇OC&;transform详解
- PHPExcel说明
- VM VirtualBox安装Centos6.5
- win10升级后蓝牙不见了,设备管理器里没有,多了个串行控制器里的未知USB设备?
- HTML XHTML HTNL5 简介
- BZOJ2973 : 石头游戏
- YFCMF 问题
- SpringBoot(十)-- 整合MyBatis
- (2)shiro角色资源权限
- MySQL 卸载
- webpack新版本4.12应用九(配置文件之configuration)
热门文章
- 洛谷 1197 [JSOI2008]星球大战
- 全文检索(AB-1)-相关领域
- 用mycat做读写分离:基于 MySQL主从复制
- DRF JWT的用法 &; Django的自定义认证类 &; DRF 缓存
- iOS 数据库操作崩溃提示“ int rc = sqlite3_step([_statement statement]);”或者提示“ rc = sqlite3_step(pStmt);”
- pycharm支持react
- 【Nginx】负载均衡-加权轮询策略剖析
- 【c++】【转】如何只在heap上创建对象,如何只在stack上建立对象?
- CLLocation的属性以及使用的解释
- yarn-cli 简介