如何找到两个节点之间具有多条边的最短路径？

Question

我正在尝试生成最短路径，但我需要生成虚拟节点来执行此操作，因为我有several edges 从伊斯坦布尔到安卡拉所以我无法使用正常方法创建路径，因为模型将这些边视为一个边。我的节点显示在 excel sheet 的前两列中（Node1 和 Node2）。我想使用 Node1_reference 和 Node2_reference 生成最短路径，但我不确定该怎么做，或者我是否应该创建虚拟节点，因为我无法调用没有后缀的城市

Answer 1

你在这里想要的是使用 nx.MultiDigraph，一个有向多重图，它可以在两个节点之间包含多个平行边。

# Add nodes
g = nx.MultiDiGraph()
g.add_node('Istanbul')
g.add_node('Ankara')
g.add_node('Muscat')

# Add edges
g.add_edge('Istanbul', 'Ankara', data=dict(time=1, route=1))
g.add_edge('Istanbul', 'Ankara', data=dict(time=2, route=2))
g.add_edge('Istanbul', 'Ankara', data=dict(time=10, route=3))
g.add_edge('Istanbul', 'Muscat', data=dict(time=20, route=1))
g.add_edge('Istanbul', 'Muscat', data=dict(time=20, route=2))
g.add_edge('Ankara', 'Muscat', data=dict(time=2, route=1))

现在我们有从一个城市到另一个城市的多条边。诀窍是指定权重函数在查询最短路径时的行为方式：https://networkx.org/documentation/stable/reference/algorithms/shortest_paths.html

def weight_func(u, v, d):
    for v in d.values():
        if v['data']['route'] == 1:
            return v['data']['time']
    return None

result = nx.shortest_path(g, source=None, target=None, weight=weight_func)
print(result)

基本上，当算法评估节点 [u, v] 之间的所有平行边时，我们得到这些边的数据属性列表，然后我们遍历它们并进行过滤，这样我们就可以 return我们想要的重量。

您可以将此函数包装在另一个 higher-level 函数中，这样更方便：

def filter_route_id(route):
    def weight_func(u, v, d):
        for v in d.values():
            if v['data']['route'] == route:
                return v['data']['time']
        return None
    return weight_func

result = nx.shortest_path(g, source=None, target=None, weight=filter_route_id(1))
print(result)

{'Istanbul': {'Istanbul': ['Istanbul'], 'Ankara': ['Istanbul', 'Ankara'], 'Muscat': ['Istanbul', 'Ankara', 'Muscat']}, 'Ankara': {'Ankara': ['Ankara'], 'Muscat': ['Ankara', 'Muscat']}, 'Muscat': {'Muscat': ['Muscat']}}

如何找到两个节点之间具有多条边的最短路径？

How to find the shortest path with multiple edges between two nodes?

python

shortest-path

nodes

networkx