2023年7月30日发(作者：)

最短路径算法综述 最短路径算法综述

更新中。。。。1.单源最短路径问题涵义：从给定的源顶点s到每个顶点v的最短路径。在弄清楚如何求算单源最短路径问题之前，必须弄掌握⼏点知识。 最短路径的最优⼦结构 最短路径算法通常依赖于⼀种性质，也就是⼀条两顶点之间的最短路径包含路径上其他的最短路径。这种最优⼦结构性质是动态规划和贪⼼算法是否适⽤的⼀个标记。Dijkstra算法是⼀个贪⼼算法，⽽找出所有顶点对之间的最短路径的Floyd_Warshall算法是⼀个动态规划算法。下⾯的引理更加准确地陈述了最短路径的最优⼦结构的性质。 引理1（最短路径的⼦路径是最短路径） 证明略，请参考《算法导论》P358 负权值边：单源最短路径的某些⽰例中，可能存在权值为负值的边。但是不可能存在负权回路。Dijkstra不能处理负权值的图，Bellman-Ford能处理。 回路：最短路径上不可能有回路。 最短路径的表⽰：已知图G=（V,E）,对于每个顶点v∈V，设置其前驱（predecessor）顶点∏（v）为另⼀顶点或NIL。通过这种⽅法，就可以使⽤PRINT-PATH(G,s,v)函数来打印路径。松弛技术（relaxation）：对于每个顶点设置⼀个属性的d[v]来描述从源点s到v的最短路径上权值的上界。具体请参考《算法导论》P360最短路径以及松弛的性质：三⾓不等式、上界性质、⽆路径性质、收敛性质、路径松弛性质、前驱⼦图性质等等。具体请参考《算法导论》P361 问题的3个变体： ♠.单终点最短路径 ♠.单对顶点最短路径 ♠.每对顶点间最短路径n-Ford算法分析与实现(C/C++)ra算法分析与实现(C/C++)(Shortest Path Faster Algorithm)算法分析与实现(C/C++)