图中的前 10 条最短路径 - Igraph 0.6 - Python 2.7

Question

自从我开始在我的编码中成功实现 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）

我知道shortest != short，虽然我需要这样的东西：如果最短没有好处，那么忽略它，转到第二个等等。我已经搜索过谷歌，但我不清楚我该怎么做。

先感谢您！

编辑：我可能会提到，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）

Answer 1

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

另一种选择是get_shortest_paths，它可以考虑权重，但它只会返回一对顶点之间的一条路径。（之所以调用它，get_shortest_paths是因为如果您指定多个目标顶点，它会返回多个路径 - 更准确地说，它为每个目标顶点提供一个路径）。因此，您无法使用get_shortest_paths获取您正在寻找的十条路径。

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