最短路径
Dijkstra算法，无负边，单源最短路径：设d[u]表示顶点u到源点的最短路径长，用优先队列的图遍历。
Bellman-Ford算法，有负边，单源最短路径：对所有边做V-1遍松弛，因为V个顶点的图中最短路径最多V-1条边。之后再对所有边做V-1遍松弛，这时若发现还有边可松弛，说明有负环。
// 对所有边做V-1遍松弛
for (i = 0; i < V - 1; i++) {
for [u,v] int graph.edges {
if (dist[u] + cost(u,v) < dist[v])
dist[v] = dist[u] + cost(u,v);
}
}
// 查负环，再对所有边做V-1遍松弛
for (i = 0; i < V - 1; i++) {
for [u,v] int graph.edges {
if (dist[u] + cost(u,v) < dist[v])
dist[v] = -INF;
}
}
Dijkstra算法和Bellman-Ford算法见单源最短路径
A*算法，就是一致代价搜索（Uniform Cost Search，UCS）+ 乐观估计。UCS类似dijkstra算法；乐观估计就是放松问题限制再估计，估计距离差h(u)-h(v) <= 真实代价cost(u,v)。写法上，除了用d[u]记顶点u到源点的最短距离，用h(u)乐观估计顶点u到汇点的最短距离，优先队列Q选f(u)=d[u]+h(u)最小的顶点来扩展。
dijkstra要求边值非负，即对u->v要求d[u]<=d[v]，作队列Q键的d值递增；A*对u->v要求h(u)<=w(u,v)+h(v)，这样f(u)=d[u]+h(u)<=d[u]+w(u,v)+h(v)=d[v]+h(v)=f(v)，作队列Q键的f值也递增。
A*搜索的有效性证明见 Stanford CS221 2019。启发式只要满足乐观估计，即对u→v有h(u)-h(v)≤cost(u,v)，估计距离差≤实际代价，A*就有效。怎么乐观估计？放松问题限制。h(x)是relaxed问题\(Cost_{relaxed}(s,a)≤Cost(s,a)\)的解。
Floyd-Warshall算法，所有点对的最短路径：设\(d_{ij}^{(k)}\)表示从顶点i到顶点j、中间顶点在集合{1, 2, ..., k}的最短路径长。根据中间顶点经不经过顶点k分为：不经过，\(d_{ij}^{(k)}=d_{ij}^{(k-1)}\)；经过，\(d_{ij}^{(k)}=d_{ik}^{(k-1)}+d_{kj}^{(k-1)}\)。所以，\(d_{ij}^{(k)}=min(d_{ij}^{(k-1)}, d_{ik}^{(k-1)}+d_{kj}^{(k-1)})\)，k=1..n。初始时，\(d_{ij}^{(0)}=w_{ij}\)是无中间顶点的情况。见ita p387。
写dp时省掉k这维，k遍历所有顶点。初始dp[i][j]=dist[i][j]，dp[i][j]=min(dp[i][j], dp[i][k] + dp[k][j])。
// 三重循环做松弛
for (int k = 0; k < N; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (dp[i][k] + dp[k][j] < dp[i][j])
dp[i][j] = dp[i][k] + dp[k][j];
}
}
}
// 查负环，再三重循环做松弛
for (int k = 0; k < N; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (dp[i][k] + dp[k][j] < dp[i][j])
dp[i][j] = -INF;
}
}
}
Floyd-Warshall算法见所有点对的最短路径