最短路

$Shortest$ $Path$

声明

为了方便叙述，这里先给出下文将会用到的一些记号的含义．

$n$ 为图上点的数目， $m$ 为图上边的数目；

$s$ 为最短路的源点；

定义

在图论中，最短路径 是指在一个加权图中，从起始顶点到目标顶点的所有可能路径中，各边上权值之和最小的那条路径

特殊情况

负环：如果图中存在一个环路，且该环路上所有边的权值之和为负数（称为“负环”），那么在这个环里无限循环会使路径总代价不断减小，此时两点之间的最短路径将不存在（趋于无穷小）

Bellman–Ford 算法是一种基于 松弛（relax） 操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断．

在国内 OI 界，下文要讲的的 SPFA ，就是 Bellman–Ford 算法的一种实现．