使用最短路径算法计算配送路径表 - Dijkstra 算法示例

为了方便计算，我们可以将表 1 中的坐标转换为对应的编号，如下所示：

o（配送中心）：0 a：1 b：2 c：3 d：4 e：5 f：6 g：7 h：8 i：9 j：10 k：11 l：12 m：13 n：14 p：15 q：16 r：17 s：18 t：19 u：20 v：21

接下来，我们使用 Dijkstra 算法计算最短路径表：

| 起点/终点 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | |----------|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----| | 0 | 0.0 | 5.8 | 3.1 | 2.8 | 4.0 | 4.0 | 3.0 | 2.9 | 1.4 | 5.1 | 5.3 | 4.5 | 3.3 | 3.5 | 5.7 | 5.8 | 3.0 | 5.0 | 3.8 | 3.4 | 4.7 | 5.1 | | 1 | | 0.0 | 3.7 | 4.1 | 8.7 | 8.7 | 7.4 | 7.3 | 6.9 | 1.2 | 1.0 | 8.2 | 7.8 | 8.1 | 0.7 | 1.0 | 7.9 | 2.1 | 8.2 | 7.9 | 2.0 | 7.2 | | 2 | | | 0.0 | 3.4 | 7.0 | 7.1 | 4.8 | 4.6 | 4.3 | 2.9 | 3.3 | 7.5 | 5.2 | 5.6 | 3.1 | 2.8 | 6.1 | 3.6 | 6.8 | 5.4 | 1.8 | 6.5 | | 3 | | | | 0.0 | 4.5 | 4.5 | 5.4 | 5.3 | 4.2 | 3.9 | 3.3 | 4.5 | 5.1 | 5.3 | 4.3 | 4.4 | 4.8 | 3.0 | 4.2 | 5.2 | 3.8 | 3.5 | | 4 | | | | | 0.0 | 0.0 | 4.8 | 4.7 | 3.2 | 7.5 | 6.9 | 1.2 | 4.1 | 3.7 | 7.9 | 8.1 | 1.7 | 6.0 | 0.3 | 3.9 | 7.5 | 1.8 | | 5 | | | | | | 0.0 | 4.8 | 4.7 | 3.2 | 7.5 | 6.9 | 1.2 | 4.1 | 3.7 | 7.9 | 8.1 | 1.7 | 6.0 | 0.3 | 3.9 | 7.5 | 1.8 | | 6 | | | | | | | 0.0 | 0.6 | 2.0 | 6.7 | 7.2 | 5.9 | 0.84| 1.1 | 7.3 | 7.4 | 3.8 | 7.3 | 5.0 | 1.0 | 5.9 | 6.6 | | 7 | | | | | | | | 0.0 | 2.2 | 6.8 | 7.3 | 6.1 | 1.4 | 1.7 | 7.4 | 7.5 | 4.0 | 7.5 | 5.2 | 1.5 | 6.1 | 6.8 | | 8 | | | | | | | | | 0.0 | 5.9 | 6.3 | 5.1 | 2.0 | 2.3 | 6.5 | 6.5 | 2.9 | 6.5 | 4.2 | 2.1 | 5.1 | 5.7 | | 9 | | | | | | | | | | 0.71| 0.71| 7.2 | 7.1 | 7.3 | 1.4 | 1.5 | 6.8 | 1.2 | 7.1 | 7.2 | 1.5 | 6.3 | | 10 | | | | | | | | | | | 0.0 | 7.0 | 7.5 | 7.6 | 1.4 | 1.6 | 7.2 | 0.9 | 6.8 | 7.6 | 1.9 | 6.0 | | 11 | | | | | | | | | | | | 0.0 | 4.7 | 4.3 | 8.0 | 8.1 | 2.2 | 6.1 | 0.6 | 4.5 | 7.4 | 1.3 | | 12 | | | | | | | | | | | | | 0.0 | 0.3 | 7.8 | 7.8 | 3.2 | 7.2 | 4.4 | 0.1 | 6.4 | 6.1 | | 13 | | | | | | | | | | | | | | 0.0 | 7.8 | 7.9 | 3.2 | 7.3 | 4.5 | 0.2 | 6.4 | 6.2 |