algorithm - 最小长度路由的最大容量

Question

在虚电路分组交换中，我们首先在网络中的源和目的地之间建立一条专用路径。路径长度最好应该很小。同样，沿着最短路径的最小链路的容量会对信息流施加限制。

因此，最好设计一个成本函数，即路径长度和最小链路容量的加权组合。由于我们想要减少路径长度 l 并想要增加最小链路容量 c_min 我们的成本函数可以是最大化 ( w₁* f( c_min) - w₂*g(l )) 其中 w₁ 和 w₂是权重，f 和 g 是线性或非线性函数。

对于任意网络中的这个问题，什么是有效的算法？？

我被这个问题困扰了一个多星期，到目前为止没有取得任何进展，我搜索了不同的方法来解决这个问题，并仔细考虑了很多，比如将它表述为最宽路径问题。但是最广泛的问题只考虑链接的容量，但是如何在问题中包含长度因素。？或者有其他方法可以解决这个问题。

Answer 1

我不认为 Dijkstra 完全没有修改就可以工作，因为中间节点看到的最佳答案不一定构成最佳整体答案的一部分:如果直接连接到目标节点的所有链路的容量都非常小，那么路由通过提供大容量而较早取得成功的方法可能毫无意义。

您可以使用 Dijkstra 找到容量至少为 X 的最短路线，方法是首先删除所有容量小于 X 的链路。如果不同的链路容量很少，您可以计算所有可能的 X 的最短路径的长度。即使有许多不同的容量，您也可以使用二分法来找到容量最大的路径。

要彻底修改 Dijkstra，我认为您最终会在每个节点处为所有可能的容量 Xi 保留到该节点的最短路径的长度，每个链接至少使用容量 Xi。