最短路径问题

最短路径问题

最短路问题是图论中一种重要的算法，本章将包括：

目录

• 最短路径问题
  
  
  
  • 一.概念
    
    
    
    • 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][j]\) ,表示 \(k\) 阶段 \(i\) 到 \(j\) 的最短路，不难发现 \(dp[k][j]\) 是由 \(dp[k-1][j]\) 推出，1.若不变，则直接继承。2.若变，则是其加借道的权值即可。由是，我们便可推出其状态转移方程：

\[dp[k][j]=min(dp[k-1][j],dp[k-1][k]+dp[k-1][k][j])\]
由状态转移方程可知， \(dp[k][j]\) 的值只与 \(dp[k-1][j]\) 有关，由是，我们可利用滚动数组将 \(dp\) 数组降维，来到二维，得到新的状态转移方程：

\[dp[j]=min(dp[j],dp[k]+dp[k][j])\]
综上，可得出 \(Flord\) 算法的核心代码。
2.代码详解

[code]for(int k=1;k