osmnx 如何知道在最短路径中绘制哪些边

Question

根据文档，边由三个参数唯一定义：u、v 和 k。所以即使 u 和 v 可以相同，参数 k 也会区分边

当我计算两个节点之间的最短路径时，我使用 nx.shortest_path。这给了我最短路径中的节点列表。

举个例子，让我们考虑节点1和2。现在我计算它们之间的最短路径，结果如下：

[1, 4, 6, 7, 2]

如果有一个 egde u=4, v=6, k=0 和另一个 u=4, v=6, k=1 我怎么知道哪一个是最短路径？ osmnx 是如何知道的，因为它可以绘制给定的最短路径？

提前致谢。

Answer 1

这似乎有两个问题。我可以回答涉及 networkx.

的部分

`Graph`:

有点迂腐（因为我想象未来的人会用谷歌搜索这个），这确实取决于您正在使用的图表类型。我们将从通用图表开始：

import networkx as nx

G = nx.path_graph(5)
G.add_edge(2, 8, weight=0.3)   # A
G.add_edge(2, 8, weight=0.6)   # B
G.add_edge(1, 8, weight=1.0)

for u, v, w in G.edges(data=True):
    print(u, v, k)

... 并考虑如果我们交换标记为 A 和 B:

的行的顺序会发生什么

import networkx as nx

G = nx.path_graph(5)
G.add_edge(2, 8, weight=0.6)   # B
G.add_edge(2, 8, weight=0.3)   # A
G.add_edge(1, 8, weight=1.0)

for u, v, w in G.edges(data=True):
    print(u, v, k)

在这两种情况下：网络看起来是一样的：

但是我们网络的参数在这两种情况下是不同的：

# A first
0 1 {}
1 2 {}
1 8 {'weight': 1.0}
2 3 {}
2 8 {'weight': 0.6}
3 4 {}

和

# B first
0 1 {}
1 2 {}
1 8 {'weight': 1.0}
2 3 {}
2 8 {'weight': 0.3}
3 4 {}

所以这里：答案是 u、v 和 k 是唯一的并且 shortest_path 返回的列表将是唯一的。

`MultiDiGraph`:

我 90% 确定问题想问的就是这种情况。在 MultiDiGraph 中，节点仍然由 u、v 索引，但可以有多个权重 k:

import networkx as nx

GM = nx.MultiDiGraph()
GM.add_edge(0, 2, weight=0.3)
GM.add_edge(0, 2, weight=0.15)
GM.add_edge(1, 2, weight=0.1)
GM.add_edge(0, 1, weight=0.1)
GM.add_edge(2, 3, weight=0.4)
GM.add_edge(2, 3, weight=0.5)

for u, v, w in GM.edges(data=True):
    print(u, v, w)

path = nx.shortest_path(GM, source=0, target=3, weight='weight')
print(path)
# [0, 2, 3]

nx.shortest_path返回的列表不明确，但是重构最小权重路径非常简单：

for u, v in zip(path[0:], path[1:]):
    edge_data = GM.get_edge_data(u, v)
    min_weight = min([edge_data[edge]['weight'] for edge in edge_data])
    print(f"{u}---({min_weight})---{v}")

结果：

0---(0.15)---2
2---(0.4)---3

Answer 2

我是 OSMnx 的开发者。听起来您是在询问其 plot_graph_route 功能。对于沿着最短路径的平行边（即某个节点 u 和某个节点 v 之间的多条边），OSMnx 会选择长度较短的边。您可以确切地看到它是如何处理这个 here.

osmnx 如何知道在最短路径中绘制哪些边

How does osmnx know which edges to plot in shortest path

python

networkx

osmnx

`Graph`:

`MultiDiGraph`:

osmnx 如何知道在最短路径中绘制哪些边

How does osmnx know which edges to plot in shortest path

python

networkx

osmnx

Graph:

MultiDiGraph:

`Graph`:

`MultiDiGraph`: