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 的容量。