1

我正在研究一个巨大的光网络项目，其中网络表示为可能存在循环的无向图。在某些时候，我想找到图中两个节点之间代表任意光学连接的所有最小跳跃路径。我成功地实现了所有边的权重为 1 的 Djikstra，以找到最小跳跃路径而不是最小权重，并修改了松弛步骤以保存节点的所有父节点而不是一个节点（添加代码以在距离相等而不是更小时保存）。所以现在在下面的示例网络中，我从节点 0 到节点 4：节点 1 有父节点 0，节点 2 有父节点 0，节点 3 有父节点 1,2，节点 4 有父节点 3。每个节点组合都是一个对象单元在二维数组中，每个单元格的许多属性之一是其父级列表（即在单元格 0 中搜索父级，

0 ---- 1
|      |
2 ---- 3 --- 4

现在我被困住了。我想以某种方式保存从图中所有源到所有目的地的所有最小跳路径，这样我就可以为任何可能的任意连接提供最小跳路径。你能推荐一个解决方案吗？我已经为此工作了好几天，但我真的被困住了。先感谢您。

4

1 回答 1

0

您的主要问题将是存储。

假设您有 10000 个节点。然后对于每个节点 N(i)，您想要存储下一个最小跳到所有可能的目的地。这意味着图中每个节点有 9999 个节点，也就是说，您需要存储 3*N^2 个节点值。

此时，从节点 N(i) 到节点 N(j) 将意味着：

k = i
while k is not j:
    h = 0
    while h < length(N(k).NextHops)
        if N(k).NextHops(h).Destination is j:
           k = N(k).NextHops(h).NextNode
           break
        else:
           h = h+1
    # if h == length of NextHops, "No Route To Host"

您可以使用 Dijkstra 初始化 NextHops（一旦找到最短路径就不会终止它）：从第一个节点开始并探索在每个节点中存储到第一个节点的距离的整个图，以及提供该距离的前一个节点。最后，元组 { Dest: i; 成本： ？; 下一个： ？} 将为所有节点初始化。如果图是连接的，则每个节点都有 N-1 个条目，因此您可以在数组的位置 i 处使用 2 元组 { Cost, Next }。

对于连通图，寻路算法变为

def findpath(i, j):
    k = i
    p = []
    c = 0
    while k is not j:
        p += i
        c += N[k].NextHops[j].Cost
        k =  N[k].NextHops[j].Next

    return { 'path': p, 'cost': c }
于 2012-10-21T11:02:06.100 回答