网格图有一个优美的性质，它的最小割的大小等于较短边的长度，不超过 $\sqrt S$，其中 $S$ 为网格图面积。
所以网格图上的最短路可以分治地做，网格上一块矩形区域，在较长边中点处切开。此时两个点间的最短路分为，只经过其中一部分的和跨过切面的。只经过其中一部分的，分治处理；跨过切面的，我们以切面上每个点为源，在整个区域内求最短路。对于一块面积为 $S$ 的矩形区域，所需时间为
$$\displaylines{T(S)=2T\left(\frac S2\right)+\sqrt S\cdot S\log S }$$根据主定理有 $T(S)=O(S^\frac32\log S)$。
设 $f_{t,u,v}$ 为只经过图中 $[1,t]\cup\{u,v\}$ 中的点，$u\to v$ 的最短路。$f_{0,u,v}$ 即 $u$ 到 $v$ 的所有边中的边权最小值，$u$ 到 $v$ 间无边即为 $+\infty$。
那么转移为 $f_{t,u,v}\xleftarrow[k]{\min}f_{t-1,u,k}+f_{t-1,k,v}$。复杂度 $O(n^3)$
维护 $d_u$，第 $t$ 轮更新时表示从起点到点 $u$ 经过不超过 $t$ 条路径的最短路。
每轮更新时遍历每条边 $(u,v,w)$，令 $d_v\xleftarrow[]{\min}d_u+w$。
这样做的正确性是显然的，考虑到若原图存在最短路，那么起点到每个点一定存在一条长度不超过 $n-1$ 的最短路。所以在经历 $n-1$ 轮更新后 $d_i$ 即为起点到 $i$ 的最短路；也即如果第 $n$ 轮更新仍然有 $d$ 变小，说明原图不存在最短路，即存在负环。
时间复杂度 $O(nm)$。
Bellman-Ford 中每轮更新会遍历一遍所有点。实际上只有上一轮中 $d$ 减小的那些点有更新其它点的能力。所以我们维护一个队列，每次取队头出来更新其它点。
显然一个点 $u$ 第 $t$ 次入队时，$d_u$ 一定小于等于 Bellman-Ford 中第 $t$ 轮更新后 $d_u$ 的值。那么一个点入队 $n$ 次说明原图存在负环。
时间复杂度 $O(nm)$。
对于一个无负权边的图，维护一个集合 $S$ 包含所有已经求得最短路的点。初始为空集。
再维护 $d_i$ 表示用 $S$ 中的点能够更新得的每个点最短路，特殊地，起点的 $d$ 值为 $0$。
每轮更新时，考察不在 $S$ 中的所有点中 $d$ 最小者 $i$，由于在 $S$ 中的点已经更新过了，不在 $S$ 中的点已经无法再更新它，所以此时 $d_i$ 即为 $i$ 的最短路。将其加入 $S$ 并更新其它所有点。
找出不在 $S$ 中的所有点中 $d$ 最小值这一步，暴力求得时间复杂度为 $O(n^2)$，使用不支持删除的堆（priority_queue）为 $O(m\log m)$，使用支持删除的堆为 $O(m\log n)$，使用支持 $O(1)$ 插入的堆（斐波那契堆、配对堆等）为 $O(n\log n+m)$。
对于无负权边的图，全源最短路可以对每个点都做一遍 Dijkstra，时间复杂度为 $O(nF(n,m))$，其中 $F(n,m)$ 为一轮 Dijkstra 的时间复杂度，若使用堆实现，其时间复杂度低于 Floyd 的 $O(n^3)$。
对于一般图没办法直接应用 Dijkstra。我们尝试给每个点 $t$ 都规定一个权值 $h_t$，并将每条边 $(u,v,w)$ 边权改为 $w+h_u-h_v$。不难发现，无论 $h$ 取什么值，新图最短路即原图最短路，且新图上 $s\to t$ 的最短路长度为原图上 $s\to t$ 的最短路长度加上 $h_s-h_t$。
为了使新图能够应用 Dijkstra，我们需要求出一组合适的 $h$ 使新图上没有负权边。即对于每条边 $(u,v,w)$ 有 $w+h_u-h_v\ge0$。于是变成了一个差分约束问题。先做一遍 SPFA 得到 $h$，修改边权，然后以每个点为起点分别做一遍 Dijkstra，最后求得原图上最短路即可。
对每个点分别求出到它最近的关键点 $f_u$，和它能到达的最近的关键点 $g_u$。
枚举每个点 $u$，如果 $f_u\not=g_u$，用 $k=\mathrm{dist}(f_u,u)+\mathrm{dist}(u,g_u)$ 更新答案。
枚举每条边 $(u,v,w)$，如果 $f_u\not=g_v$，用 $k=\mathrm{dist}(f_u,u)+w+\mathrm{dist}(v,g_v)$ 更新答案。
不难发现上述每个用以更新答案的值 $k$ 都对应着至少一条合法路径，所以我们只需要证明 $k$ 至少一次取到正确答案。
考察所有起点和终点均为关键点的路径中最短的一条 $p_0,p_1,p_2\cdots,p_{m}$，设其长度即原问题答案为 $t$，那么我们有以下结论：
否则不满足 $f$ 或 $g$ 的定义。
由此结论可以得出，我们的更新方法中 $k$ 取不到正确答案 $t$，当且仅当这条路径上的每个点 $u$ 都有 $f_u=g_u$，每条边 $(u,v,w)$ 都有 $f_u=g_v$。那么
$$\displaylines{f_{p_0}=g_{p_1}=f_{p_1}=g_{p_2}=\cdots=g_{p_{m-1}}=f_{p_m} }$$而我们又显然有 $f_{p_0}=p_0\not=p_m=f_{p_m}$。矛盾，所以我们的更新方法一定能够取到正确答案。
解 $n$ 元一次不等式组，每个不等式形如 $x_i-x_j\le k$。
用最短路的性质（$(u,v,w)\in G\Rightarrow \operatorname{dis}_v\le\operatorname{dis}_u+w$）保证解符合方程（最长路同理）。
如果只要求判定是否有解，3、4 步删去，用 SPFA 判定是否有负环/正环。
因为建完图之后任意边的边权非负，所以一个环内出现正权极为无解，强连通分量缩点后拓扑排序求最长路。