最短路径(Dijkstra、Floyd)

Dijkstra算法

Dijkstra算法是建立在贪心思想之上的，它是解决单源最短路径问题的经典算法之一。其核心思路是每次都选取距离源点最近的顶点，接着更新其邻接点的最短路径长度。一旦某个顶点的最短路径被确定，该顶点就会被标记，表示其最短路径长度不再需要更新。

需要注意的是，Dijkstra算法不适用于含有负边权的图的最短路径问题。

Dijkstra算法在每次选择路径时会采取贪心策略，优先考虑当前邻接的点，而不是考虑更远的点。

如果图中不存在负权边，Dijkstra算法适用于所有情况，因为它基于贪心策略，每次都选取距源点最近的点，将其作为到源点的最短路径。然而，若存在负权边，则直接得到的最短路径可能并非真正最短，因为可能存在通过非最近点再通过负权边使得路径之和更小的情形。例如，使用Dijkstra算法处理1——>5的最短路径，可能得到的结果为5，即1——>2——>4——>5，但实际上1——>5的最短路径是1——>3——>4——>5，其长度为4。

如果图中存在负环，则意味着最短路径不存在。因为可以在负权环上不断循环，得到任意小的最短路径长度，负数的绝对值越大，这个值就越小。

算法实现包括普通版和堆优化版。

Floyd算法

Floyd算法是基于动态规划的多源最短路径算法，可以求图中任意两个点之间的最短路径。它可以处理含负边权的有向（无向图）的最短路径问题，其应用范围比Dijkstra算法更广，时间复杂度为[公式]。

算法思路是通过以k个顶点作为中转逐个更新任意两个顶点之间的最短路径。可以将其抽象为矩阵D和辅助矩阵S，其中矩阵D的元素[公式]表示顶点[公式]到顶点[公式]的距离[公式]，如果两个点没有连边，则相应元素是无穷(∞)，矩阵S的元素[公式]，一般用于查找最短路径的具体路径方案。

算法流程如下：

若满足条件[公式]，则进行以下操作：

举个荔枝：

由上述模拟过程可知，第k层答案依赖于第k-1层，即具有最优子结构性质，且当前状态是前面已经确定状态的完美总结。因此，问题转化为自底向上的动态规划问题。

定义[公式]

算法实现：