自从我开始在我的编码中成功实现 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 尝试同样的事情)