最短路问题

最短路问题（Shortest Path Problem, SPP）是一类非常经典的问题。最短路问题可以描述为：给定一个有向图（或无向图）， 是图中点的集合， 是图中边的集合。图中的每条边 都对应一个权重 。给定一个起点 （）和一个终点 （），最短路问题就是要找一条从 出发、到达 的、总距离或总成本最小的路径。最基本的最短路问题并不是 NP-hard 问题，可以用 Dijkstra 等算法在多项式时间内求得最优解（Dijkstra et al., 1959），Dijkstra 算法的复杂度为 ，并且在不同数据结构下，复杂度会略有不同。

注：图算法视角的实现与变体可参见本站 Dijkstra；本页仅写数学模型与 LP 松弛形式。

一、0–1 决策变量

最短路问题可建模为（线性）整数规划。先引入 0–1 决策变量 表示有向边 是否被选入 – 最短路。若将每条有向边记为 ，则下式中的 与 一一对应。

在以下以边集 为下标求和的写法中，记 为边 上距离或成本， 表示该边是否选用。

二、整数规划模型

目标为选取一条从 到 的 – 路，使所经过边的 之和最小：

流量守恒（源汇型）为：对每个节点 ，流出减流入在 处为 1、在 处为 -1、对其余节点为 0。

注：上式中 表示自节点 出发的边 的全体， 表示进入 的边 的全体（与常见网络流记法中「出弧 / 入弧」的约定一致）。无向边在「最短路 as 0–1 子图」的写法里，常把无向边 用两条有向弧 与 表示，并令 与权重一致；在「边变量 只表示是否选边」的 ILP/关联矩阵写法里，则对每条无向边 用单个 与节点–边入射关系写平衡。两种都可在有向/无向同一实例上得到同一最短路，依实现择一写全即可（下文第二节起按有向弧 写完整 LP）。

三、约束的等价写法

(2) 也可写为带统一右端 的净供给形式（便于与网络流、LP 标准形对照）：

其中

• 当 时，；
• 当 时，；
• 当 为其余节点时，。

四、整数最优解特性与 LP 松弛

该模型具有整数最优解特性（与「松弛后仍存在整数最优解」的叙述一致；理论细节可参见 最优整数解特性与幺模矩阵 及 Cappanera and Scaparra, 2011）。具体而言，即便将 0–1 变量 松弛为在 上取值的连续变量（即

），在适当条件下仍存在整数最优解，因而整数规划与盒约束下线性规划在最优解意义上可讨论等价性。理论背景见 最优整数解特性与幺模矩阵。

五、等价的线性规划形式

由上述性质，在「考虑 LP 解仍为整数最优点」的语境下，可将模型写为下述线性规划（目标与 (1) 相同、约束为 (4) 与 ）：

其中 与 (4) 中相同：、、其余为 0。

注：上列 (1)–(7) 是「最短路 as 0–1 路径流 / LP 松弛」的常见写法。实现时需注意有向边方向与 的唯一定义，以保证可复现性。