§3最短路问题 在实践中常遇到的一类网络问题是最短路问题。给定一个有向 赋权图D=(V,A)，对每一个弧a=(,)，相应有权o≥0，指 定D中的v,为发点，v,为终点。最短路问题就是要在所有飞，到，的路 中，求出一条总权数最小的路。这里权数可以是距离，也可以是时 间，或者是费用等等。 最短路问题是最重要的优化问题之一，它不仅可以直接应用于 解决生产实际的许多问题，如管道铺设、线路安排、厂区布局、设 备更新等等，而且经常被作为一个基本工具，用于解决其它优化问 题。 §3 最短路问题 在实践中常遇到的一类网络问题是最短路问题。给定一个有向 赋权图D=（V，A），对每一个弧a =（vi ,vj），相应有权ωij ≥0，指 定D中的vs 为发点，vt 为终点。最短路问题就是要在所有vs 到vt 的路 中，求出一条总权数最小的路。这里权数可以是距离，也可以是时 间，或者是费用等等。 最短路问题是最重要的优化问题之一，它不仅可以直接应用于 解决生产实际的许多问题，如管道铺设、线路安排、厂区布局、设 备更新等等，而且经常被作为一个基本工具，用于解决其它优化问 题