0

自从我开始在我的编码中成功实现 Igraph 以来,我一直在想这个问题:你能用get_all_shortest_paths检索尽可能多的最短路径吗?让我们说前10个。

到目前为止,我已经理解在无向图中检索所有最短路径是没有意义的,因为在大多数情况下,您拥有无限数量的路径。

但是我可以简单地检索前 10 条最短路径吗?

我试图用无向的 g = Graph() 来实现这一点:

list = []
list.append(g.get_all_shortest_paths(index1,index2, "distance")[0])   # shortest path
list.append(g.get_all_shortest_paths(index1,index2, "distance")[1])   # second shortest path
list.append(g.get_all_shortest_paths(index1,index2, "distance")[2])   # third shortest path
list.append(g.get_all_shortest_paths(index1,index2, "distance")[3])   # forth shortest path
list.append(g.get_all_shortest_paths(index1,index2, "distance")[4])   # fifth shortest path
list.append(g.get_all_shortest_paths(index1,index2, "distance")[5])   # sixth shortest path
list.append(g.get_all_shortest_paths(index1,index2, "distance")[6])   # seventh shortest path
list.append(g.get_all_shortest_paths(index1,index2, "distance")[7])   # eigth shortest path
list.append(g.get_all_shortest_paths(index1,index2, "distance")[8])   # ninth shortest path
list.append(g.get_all_shortest_paths(index1,index2, "distance")[9])   # tenth shortest path

#"distance" is from g.es["distance"]

列表索引超出范围总是会给我错误。实际上我什至无法得到list.append(g.get_all_shortest_paths(index1,index2, "distance")[1]),虽然我知道那里有超过 10 条路径。

图表没有什么特别之处。数以千计的顶点,都以某种方式连接,我的意思是各种顶点度数。

最后我想有一个 wx.spin 或 wx.ComboBox 在路径之间进行选择(即现实生活中最短的国道在冬天结冰,所以我想在 City1 之间走第二最短的路和 City2 ......然后哦不......有袋鼠在上面跳,所以我选择第三条,或者更好的第四条路,因为我知道麦当劳,我真的很喜欢吃垃圾食品 bla bla)

我知道最短!= 短,虽然我需要类似的东西:如果最短不好,那么忽略它,转到第二个等等。我已经搜索了谷歌,但我不清楚我该怎么做。

先感谢您!

编辑:我可能会提到,list.append(g.get_all_shortest_paths(index1,index2, "distance")[1])当恰好有 2 条最短路径自然具有完全相同的距离时,这当然是有效的。

重要更新:

由于我无耻地误解g.get_all_shortest_paths了这部分将在我的代码中更改为,g.get_shortest_paths(index1, index2, weights=distance, mode=ALL, output="vpath")并且我还提到该图是加权的,但无论如何这一点是显而易见的:

list = []
g.es["weight"] = distance
list.append(g.get_shortest_paths(index1, index2, weights=distance, mode=ALL, output="vpath")[0])   # shortest path
list.append(g.get_shortest_paths(index1, index2, weights=distance, mode=ALL, output="vpath")[1])   # second shortest path
list.append(g.get_shortest_paths(index1, index2, weights=distance, mode=ALL, output="vpath")[2])   # third shortest path
list.append(g.get_shortest_paths(index1, index2, weights=distance, mode=ALL, output="vpath")[3])   # forth shortest path
list.append(g.get_shortest_paths(index1, index2, weights=distance, mode=ALL, output="vpath")[4])   # fifth shortest path
list.append(g.get_shortest_paths(index1, index2, weights=distance, mode=ALL, output="vpath")[5])   # sixth shortest path
list.append(g.get_shortest_paths(index1, index2, weights=distance, mode=ALL, output="vpath")[6])   # seventh shortest path
list.append(g.get_shortest_paths(index1, index2, weights=distance, mode=ALL, output="vpath")[7])   # eigth shortest path
list.append(g.get_shortest_paths(index1, index2, weights=distance, mode=ALL, output="vpath")[8])   # ninth shortest path
list.append(g.get_shortest_paths(index1, index2, weights=distance, mode=ALL, output="vpath")[9])   # tenth shortest path

#"distance" is a list containing the weights
# graph is TRUE-ly weighted now

如何获得两个顶点之间的前 10 条或所有短路径?

这个问题仍在寻找被接受的答案。谢谢你。

(PS 我在问题的第一部分中一直使用错误的方法,因为可能有其他像我这样的巨大的 idiobooms 尝试同样的事情)

4

1 回答 1

5

好的,我仍然不确定您所说的“前 10 条最短路径”是什么意思,但这是我认为您可能想要实现的目标。您有一个图表,其中边缘由两个端点的实际(例如,欧几里得)距离标记。你得到两点,你希望在它们之间找到一些替代路径,同时尽量保持这些路径尽可能短。请注意,由于您的图表是加权的,所以两点之间不太可能有许多最短路径 - 为了使所有路径都是最短的,它们必须完全具有相同的总重量。如果您的权重“像乌鸦飞翔”那样测量实际距离,那么这种同时发生的情况就不太可能发生——您要寻找的十条路径的长度会略有不同。因此,get_all_shortest_paths对您没有用处,不仅因为它不使用权重,还因为即使使用权重,您也不太可能在长度完全相同的两点之间找到多条路径。

另一种方法是get_shortest_paths,它可以考虑权重,但它只会返回一对顶点之间的一条路径。(之所以调用它,get_shortest_paths是因为如果您指定多个目标顶点,它会返回多个路径 - 更准确地说,它为每个目标顶点提供一个路径)。所以,你不能用它get_shortest_paths来获得你正在寻找的十条路径。

经过一番谷歌搜索,我找到了一个可能对您有用的 k-shortest-paths 算法的实现。它不是 的一部分igraph,但您可以保存您的图形,使用 Python中的模块igraph调用 k-shortest-paths 算法的编译可执行文件,然后以某种方式解析结果。os.systemsubprocess

于 2013-04-05T14:21:48.160 回答