最短路径问题
最短路径问题最短路问题是图论中一种重要的算法，本章将包括：
目录
[*]最短路径问题
[*]一.概念
[*]1.概念
[*]2.解决方案
[*]二. \(Flord\) 算法
[*]1.算法思想
[*]2.代码详解
[*]3.算法应用及局限性
[*]二. \(Djikstra\) 算法
[*]1.算法思想
[*]2.代码详解
[*]3.算法特征及其局限性
[*]三. \(Bellman-ford\) 算法
[*]1.算法思路
[*]2.代码详解
[*]3.算法特性
[*]四. \(SPFA\) 算法
[*]1.算法思想
[*]2.代码详解
[*]3.特征及性质
[*]五.总结
一.概念
1.概念
一张图中n条点和m条边，边都有权值，权值可正可负。边可能有向，可能无向，给定起点s和终点t，在所有能链接s和t的路径中，寻找所经权值最小的路径，此为最短路径问题。
2.解决方案
最容易想到的方法是暴力法，枚举所有路径，再进行大小比较，但明显不可行，一定会超时。
更好的方法即为在寻路的过程中，动态规划将要走的最短路径，此也为下文的算法思路和方法。
二. \(Flord\) 算法
\(Flord\) 算法是最简单的最短路径算法，甚至短于暴力搜索。
1.算法思想
求 \(i\) 到 \(j\) 的最短路径,对于其他所有点，每个点 \(k\) 都尝试一遍能否 \(i\) 借道 \(k\) 到 \(j\) 会不会更短。
对于这样的思路，我们可以用动态规划来解决，定义 \(dp\) ,表示 \(k\) 阶段 \(i\) 到 \(j\) 的最短路，不难发现 \(dp\) 是由 \(dp\) 推出，1.若不变，则直接继承。2.若变，则是其加借道的权值即可。由是，我们便可推出其状态转移方程：
\=min(dp,dp+dp)\]
由状态转移方程可知， \(dp\) 的值只与 \(dp\) 有关，由是，我们可利用滚动数组将 \(dp\) 数组降维，来到二维，得到新的状态转移方程：
\=min(dp,dp+dp)\]
综上，可得出 \(Flord\) 算法的核心代码。
2.代码详解
for(int k=1;k
页:
[1]