图论 之 最短路

(读者在学习本博客之前，请先学习 " 图 " 哦~。)

---

一. 回顾

1. 图的储存

让我们来复习一下图的储存：

2. 图的遍历

• 深度优先遍历 $(dfs)$(dfs)
  访问标记避免重复 $vis[N]、add$vis[N]、add_$edge(起点,终点)$edge(起点,终点) {$G[v].push$G[v].push _ $back(u)$back(u);无向反向}
• 广度优先遍历 $(bfs)$(bfs)
  队列、优先队列(字典序)
• 拓扑排序
  判定有向无环图 $(DAG)$(DAG)

---

二. 最短路

最短路径问题是图论研究中的一个经典算法问题，旨在寻找图 (由结点和路径组成的) 中两结点之间的最短路径。

1. 概念

最短路问题：给出一个带权图，再给出起点和终点，求出起点到终点的最少权值。
求最短路的方法有很多种，兔兔在这里给大家介绍常用的几种：

• $Floyd$Floyd 算法
• $Dijkstra$Dijkstra 算法
• $Bellman-Ford$Bellman−Ford 算法

2. $Floyd$Floyd 算法

$Floyd$Floyd 算法的本质就是动态规划：
把中转点当作当前的阶段。
$F[k,i,j]$F[k,i,j] 表示：在 $i$i 到 $j$j 的中转点为标号 $1$1 ~ $k$k 这些点时，从 $i$i 到 $j$j 的最短路的值
$F[0,i,j] = dis[i,j]$F[0,i,j]=dis[i,j]，$dis$dis 为前面定义的邻接矩阵
$F[k,i,j] = min(F[k-1,i,j]$F[k,i,j]=min(F[k−1,i,j], $F[k-1,i,k]+F[k-1,k,j])$F[k−1,i,k]+F[k−1,k,j])
k这一维空间可以省略，变成F[i,j]
由于 $k$k 是 $DP$DP 的阶段循环，所以 $k$k 循环必须要放在最外层
就成为了我们平时常见的 $Floyd$Floyd 算法
$Floyd$Floyd 算法 是最简单，也是容易理解的最短路径算法，可以计算图中任意两点间的最短路径。
时间复杂度为 $O(N^3)$O(N3)，适用于 $正负边权$正负边权 的情况。

---

附: 未完结

• 兔兔的博客还没有完结哈，请读者们见谅哦~
• 如果读者有 $想要作者改进的地方$想要作者改进的地方 或者 $想要作者添加的$想要作者添加的，请在 $评论区留言$评论区留言 或者 $给兔兔私信$给兔兔私信 哦~