最短路问题的探究及其lingo求解

作者：张俊青

来源：江西电力职业技术学院学报, 2023, 36(08): 40-42.

• 最短路
• 0-1规划法
• 动态规划法
• 拓扑排序

最短路问题是图论中的一个典型问题，在实际生活中应用广泛。从实例出发，探讨了有向赋权图中最短路问题的两种求解方法，即0-1规划法和动态规划法，详细剖析了其理论依据，并建立了lingo求解模型，实现了快速求解。特别是动态规划法，通过引入拓扑排序，解决了复杂有向赋权图的阶段划分问题，极大地拓展了动态规划法的应用范围。

• 单位
  山西职业技术学院