我怀疑这对于运行时间是否最佳，但是：
- 在图G上使用Dijkstra算法获取路径P
- 对于路径P中的所有边E：
- -如果未连接G-E，则继续下一个边沿（转到2）
- -在G-E上使用Dijkstra的算法找到路径X_i
- -如果当前X_i的长度小于所有其他X_i的长度，请保存它
- for循环末尾的X_i是第二个最短路径
第二最短路径无法通过P中的所有边，但有可能通过其中所有之一。我以“第二最短路径”假设您不多次使用边，否则第二最短路径可能包含P。
我怀疑这对于运行时间是否最佳，但是：
第二最短路径无法通过P中的所有边，但有可能通过其中所有之一。我以“第二最短路径”假设您不多次使用边，否则第二最短路径可能包含P。
名师互学网 版权所有 (c)2021-2022 ICP备案号：晋ICP备2021003244-6号
