本文共 1092 字，大约阅读时间需要 3 分钟。

最短路径算法中，Dijkstra算法是最常用的解决方案。然而，在某些情况下，题目会要求不仅找到最短路径，还需要在多条最短路径中选择第二标尺最优的路径。这种情况下，通常会引入三种不同的出题方法来解决问题。

第一种方法：增加边权

在这种方法中，除了原始的边权G[u][v]外，我们会为每条边增加一个额外的边权cost[u][v]。目标是通过求解最短路径时，路径上的总花费（cost之和）最小。如果需要最大化花费，也可以将cost[u][v]定义为最大值。

为了实现这一点，我们需要在Dijkstra算法中引入一个额外的数组c[]，其中c[u]表示从起点s到达顶点u的最少花费。初始化时，c[s]设为0，其余顶点的c值设为无穷大。在Dijkstra算法的更新步骤中，不仅要比较G[u][v]，还要比较c[u] + cost[u][v]。具体来说：

• 如果d[u] + G[u][v] < d[v]，则更新d[v]和c[v]。
• 如果d[u] + G[u][v] == d[v]，但c[u] + cost[u][v] < c[v]，则更新c[v]。

第二种方法：新增点权

在这种方法中，我们为每个顶点增加一个点权weight[u]，例如表示该顶点可以收集到的物资数目。在多条最短路径中，目标是找到路径上的总点权之和最大的路径。

为此，我们引入一个额外的数组w[]，其中w[u]表示从起点s到达顶点u的总点权。初始化时，w[s]设为weight[s]，其余顶点设为0。在Dijkstra算法的更新步骤中，不仅要比较G[u][v]，还要比较w[u] + weight[u][v]。具体来说：

• 如果d[u] + G[u][v] < d[v]，则更新d[v]和w[v]。
• 如果d[u] + G[u][v] == d[v]，但w[u] + weight[u][v] > w[v]，则更新w[v]。

第三种方法：计算最短路径条数

在这种方法中，我们需要确定从起点s到终点v的最短路径有多少条。为此，我们引入一个额外的数组num[]，其中num[u]表示从起点s到达顶点u的最短路径条数。初始化时，num[s]设为1，其余顶点设为0。

在Dijkstra算法的更新步骤中：

• 如果d[u] + G[u][v] < d[v]，则更新d[v]，并将num[v]设为num[u]。
• 如果d[u] + G[u][v] == d[v]，则将num[v]加上num[u]。

通过以上三种方法，我们可以根据题目需求选择合适的解决方案。在代码实现中，只需要在Dijkstra算法的更新步骤中适当修改，引入相应的数组即可完成任务。