最短路算法不再赘述，假定我们已经求出了最短路，记 \(f[x, y]\) 为 \(x\) 到 \(y\) 的最短路。
记 \(g[x, y]\) 为 \(x\) 到 \(y\) 的次短路。
最短路和次短路的性质
假定图中不存在0环。
- 任何一条最短路的路径中，一定不经过重复的点。
假设出现了，那就是一个环，因为没有0环和负环，去掉之后一定更小，与它是最短路径矛盾。
- 任何一条次短路中，重复的点出现的次数一定不超过2次
同样，如果出现了至少3次，那么就会出现多于2个正环。全部正环去掉之后，就是最短路径；只保留一个正环，此时路径长度（记为 \(cur\)）严格大于最短路径；而此路径上有两个正环，它一定大于 \(cur\)。
也就是存在一个路径 \(x\) ，使得最短路 \(d < x < y\)，那么 \(y\) 肯定就不是次短路了，因为次短路是除了最短路外最小的一条路径。
这些性质也许有用，也许没用
次短路的求法
我们将最短路树（就是那个DAG）建出来，设为 \(G\)。
那么，非最短路径一定有一条边不在 \(G\) 中。
假设所有边都在 \(G\) 中，而最短路树保证了走到每个点的路径长度都是起点到它的最短路，这就与此路径为非最短路径矛盾。
我们要求的就是所有非最短路径的长度构成的集合 \(S\) 中的最小值。
将 \(S\) 按照从起点出发，第一条不在 \(G\) 中的边 分类。
假设当前求的是从起点出发，第一条不在 \(G\) 中的边是 \((u, v)\) 的最小值。
需要注意，不论是无向图还有有向图，走的路径都是有顺序的，所以 \(G\) 中都是有向边。
条件限制了一定经过 \((u, v)\) 而从起点到 \(u\)，从 \(v\) 到终点的走法都是相对独立的，因此此子集的最小值就是 \(f[start, u] + w(u, v) + f(v, end)\)。
枚举每一条不在 \(G\) 中的边 \((u, v)\)，\(S\) 的最小值就是 \(f[start, u] + w(u, v) + f(v, end)\) 的最小值。
这样就求出了次短路。