还剩6页未读,继续阅读
文本内容:
《最短路问题》课件PPT欢迎来到最短路问题的世界在本课件中,我们将介绍四种最短路算法及其应用,并分析它们的优缺点问题背景什么是最短路问题?为什么需要解决最最短路问题的历史123短路问题?渊源最短路问题是计算从源很多实际问题都涉及到最短路问题最早由荷兰节点到目标节点的最短最短路径的计算,比如数学家Edsger Dijkstra路径的问题它是图论电网、交通、通信等领在年提出1956中的一个经典算法问题域最短路问题的定义图论中的最短路问什么是路径长度?什么是无环图?题指什么?路径长度是指路径上边或弧无环图指不存在环的图,可的权值之和以用拓扑排序求解最短路在无向连通图或有向连通图中,从某一起点到其余各顶点的最短路径最短路问题的应用城市交通规划数据通信电网规划求出两个城市之间的最短路径,在计算机网络中,最短路算法通过求解最短路径,优化电网方便交通规划与管理常用于路由选择的布局,提高供能质量最短路算法的分类算法算法Dijkstra Bellman-Ford算法解决的是带权有向图的单源最短算法解决的是有向图中含有负Dijkstra Bellman-Ford路径问题权边的单源最短路径问题算法算法Floyd-Warshall A*算法解决的是所有点对之间算法综合了贪心和广度优先搜索,在启发Floyd-Warshall A*的最短路径问题,可以处理有向图或负边权函数的帮助下,可以高效解决带权图上的单图源最短路径问题算法示例1Step1假设我们要求从点到其他各点的最A短路径Step22首先初始化点到其他各点的距离为A无穷大,点到自身的距离为A03Step3找到点的直接邻居,更新其距离值AStep44重复,直到所有节点的距离值Step3都已经更新总结最短路问题的应用广泛不同算法有各自的特点它能够优化各种系统的工作效率,满足社会和比如算法计算速度快,但不能处理负权Dijkstra人民的需求边;而算法能处理负权边,但时Floyd-Warshall间复杂度较高谢谢观看更多内容欢迎访问我的博客。