2

我只是想确保这会奏效。你能找到使用 Dijkstra 算法的最佳路径吗？您是否必须先将距离初始化为-1，然后更改relax 子例程以检查它是否更大？

这是一个不会有任何负权重的问题。

这实际上是问题所在：

假设给定一个电话网络图，它是一个图 G，其顶点代表交换机中心，其边代表两个中心之间的通信线路。边缘由其最低带宽边缘的带宽标记。给出一个算法，给定一个图表和两个开关中心 a 和 b，将输出 a 和 b 之间路径的最大带宽。

这行得通吗？

编辑：

我确实找到了这个：

提示：基本子程序与 Dijkstra 中的 Relax 子程序非常相似。假设我们有一条边 (u, v)。如果 min{d[u],w(u, v)} > d[v] 那么我们应该将 d[v] 更新为 min{d[u],w(u, v)} （因为从 a 到u 然后到 v 的带宽为 min{d[u],w(u, v)}，比我们目前的带宽还要多）。

不完全确定这意味着什么，因为所有距离在初始化时都是无穷大的。所以，我不知道这将如何工作。任何线索？

4

6 回答 6

1

我不确定 Djikstra 是要走的路。负重对 Djikstra 做坏事、坏事。

我认为您可以按边权重排序，然后开始删除权重最低的边（最严重的瓶颈），并查看图形是否仍然连接（或者至少是您的起点和终点）。图表被破坏的点是当您知道您消除了瓶颈时，您可以查看该边缘的值以获取带宽。（如果我没记错的话，每次迭代都需要 O(E) 时间，并且您需要 O(E) 次迭代才能找到瓶颈边缘，所以这是一个 O(E 2 ) 算法。

编辑：您必须意识到最大路径不一定是最高带宽：您正在寻求最大化 的值min({edges in path})，而不是sum({edges in path}).

于 2011-04-18T04:02:35.327 回答
1

您可以通过修改 Dijkstra 计算所有其他顶点的最大带宽来轻松解决这个问题。

您不需要将起始顶点初始化为 -1。

Algorithm: Maximum Bandwidth(G,a)

Input: A simple undirected weighted graph G with non -ve edge weights, and a distinguished     vertex a of G

Output: A label D[u], for each vertex u of G, such that D[u] is the maximum bandwidth available from a to u.


Initialize empty queue Q;
Start = a;
for each vertex u of G do,
   D[u] = 0;

for all vertices z adjacent to Start do{                              ---- 1

 If D[Start] => D[z] && w(start, z) > D[z] {
    Q.enqueue(z);
    D[z] = min(D[start], D[z]);
  }
}
If Q!=null {
   Start = Q.dequeue;
   Jump to 1

}

else
  finish();

这可能不是计算带宽的最有效方法，但它是我现在能想到的。

于 2012-04-17T18:21:33.940 回答
0

计算流量可能更适用，但是流量允许使用多个路径。

于 2011-04-18T04:00:56.823 回答
0

只需反转边缘权重。也就是说，如果边缘权重为 d，则将其视为 d^-1。然后像往常一样做 Dijkstra。像往常一样将所有距离初始化为无穷大。

于 2011-04-18T04:04:31.727 回答
0

您可以使用 Dijkstra 的算法找到一条最长的路径，但由于您只有两个交换中心，我不明白为什么需要像 Dijkstra 那样访问每个节点。最喜欢的是一种更优化的方法，例如分支定界算法。

于 2011-04-18T04:07:46.103 回答
0

你能调整算法 AllPairsShortestPaths(Floyd-Warshall) 中的一些逻辑吗？ http://www.algorithmist.com/index.php/Floyd-Warshall%27s_Algorithm

将未连接的边初始化为负无穷大，而不是取距离的最小值取最大值？

于 2015-03-28T16:51:06.140 回答