最小化最大距离

Question

我正在尝试使用 NetworkX 来最小化从 s -> v 的路径中的最大距离：我的想法是在排序边的容器中进行 for 循环。我会一次添加一条边，检查是否已创建从 s -> v 的路径。我的图表的节点是（城市，州），每个节点之间的距离作为我的边缘。我的代码如下。我不太清楚从这里该怎么做。到目前为止，这是我要测试的，它只给我返回一条路径（最小加权边的路径）。如果我能取回它，我将提取最小边缘并显示。节点和边权重都是从文件中读入的。然后，用户能够通过从一个距离到另一个距离的范围内的各种属性和边缘 select 城市。虽然我认为我的循环应该在找到第一条路径后中断，但它会继续运行并显示所有路径。

def MinMaxDist(self):
    edges = []
    for edge in self.selected_edges:
        edges.append(edge)
    edges = sorted(edges)

    while True:
        print("Input source and targe nodes in the following format: Yankton, SD")
        source = str(input("Enter a source: "))
        target  = str(input("Enter a target: "))
        if not source:
            break
        try:
            for edge in edges:
                self.graph.add_path([edge])
                if nx.all_simple_paths(self.graph, source, target):                   
                    print(list(nx.all_simple_paths(self.graph, source, target)))               
                    break
         except:
             print("No path from %s to %s" (source, target))

Answer 1

您只跳出 for 循环，而不是在遍历边时跳出 while 循环。一个break只突破一级。这是您想要 return 以便整个函数停止执行的时间。

我还想进行另一项更 Pythonic 的更改。每个 for 循环都有一个 else: 代码，只有当你没有跳出循环时才会执行。

def MinMaxDist(self):
    edges = sorted([edge for edge in self.selected_edges])

    while True:
        print("Input source and targe nodes in the following format: Yankton, SD")
        source = str(input("Enter a source: "))
        target  = str(input("Enter a target: "))
        if not source:
            break
        for edge in edges:
            self.graph.add_path([edge])
            if nx.has_path(self.graph, source, target):                   
                print(list(nx.all_simple_paths(self.graph, source, target)))               
                return
        else:
            print("No path from %s to %s" (source, target))

最小化最大距离

Minimize the Max Distance

graph

networkx

python-3.x