最短路径算法

最短路径问题：给定有向图$G = V, SA$用n表示图G的顶点数n = V,用m表示图中的边数m = A,选中图中的一个顶点为源点s,对每条有向边$i,j \ in A$,给其一个权重值$c_{ij}$

• 从顶点s到顶点i的非空路径P是一个有向边序列：$s, j_1, j_1, j_2,\dots, j_n,i$,路径也表示为$s \rightarrow j_1 \rightarrow j_2 \rightarrow \dots \rightarrow i$

用$cP$表示路径P中的所有权重之和
若$di$表示所有$s\rightarrow i$路径权重之和的最下值，则称路径为最短路径，若图中不存在$s\rightarrow i$的路径，则置$di$为$\infty$

• 若路径中没有重复的顶点，则称为简单路径
• 若路径起止于同一个顶点，则称之为回路

无负权边 Dijkstra算法

当所有边$i,j \in A$都有$c_{ij} > 0$,可用dijkstra算法来求解最短路径

该算法对图中顶点保存一个距离标记d,$d_i$是最短$s \rightarrow i$路径的距离预估数值，称为$s \rightarrow i$路径的距离

伪代码

输入：G = V,A, $\forall_{ij \in A}, c_{ij} \geq 0, s \in A$
输出：$di$和$pi, \forall_i \in A$

for all $i \in V$ do $di \leftarrow \infty, pi \leftarrow null$
$ds \leftarrow 0$
while所有顶点没有被标注完 do
$\quad$在所有未标注的点选择i,使得$di$最小，并标注i
$\quad$for $j \in A$ && $i,j \in A$ do
$\quad\quad$if $dj > di + c_{ij}$
$\quad\quad\quad dj = di + c_{ij}$
$\quad\quad\quad pj \leftarrow i$

有负权边 Bellman-ford算法

负权回路的检测算法