如何找到不包含特定边的最短路径？

Question

我在用Py2neo，不过这可能不太重要，因为这件事大概需要通过写Cypher查询来完成。

简单来说，我想在一个子图中找到最短路径，这个子图几乎包含整个图，只是去掉了很小一部分的边（比如说百万分之一或者更少）。

举个例子，假设我有节点A、B和C，还有边(A->B)、(A->C)、(B->C)。当然，从A到C的最短路径是直接连接。但是如果我想找一条不使用那条边的最短路径，那就得是A B C了。

另外，这个功能是用户在一个多用户的（网页）应用中可以指定的。所以我不能真的去改数据库……如果这不是问题的话，我可以在边上创建一个属性“allow: true/false”，然后把它设为false，但那样会影响到所有当前用户的应用行为。

还有一种变体是可以在边上存储“disallow: sessionID1, sessionID230, sessionID1010”，也就是说，实际记录哪些应用会话想要排除那条边，但这似乎也不是个理想的方案。

当然，我可以在Python中实现广度优先搜索（BFS），通过从neo4j获取需要的节点，并把它们放在一个队列里，而不是让neo4j来做搜索，但这样做肯定会慢很多，对吧？

有什么想法吗？谢谢

编辑：请求查看代码。

下面是我目前如何在两个节点之间获取最短路径的代码，我是先在索引中查找节点。现在想象一下，还有一份需要在最短路径搜索中忽略的边的列表（也就是独特的关系）。

from py2neo import neo4j

g = neo4j.GraphDatabaseService()

def shortest_path(a, b):
    a = g.get_indexed_node("worddex", "word", a)
    b = g.get_indexed_node("worddex", "word", b)
    if not a and b: return None
    query_string = "START beginning=node(%d), end=node(%d) MATCH p = shortestPath(beginning-[*..100]-end) RETURN p" % (a._id, b._id)
    result = neo4j.CypherQuery(g, query_string).execute()
    if not len(result): return None
    p = result[0].p
    ret = []
    for node in p.nodes:
        ret.append(node["word"])
    return ret

编辑2：示例控制台：http://console.neo4j.org/r/3c1rgn

在任何两个人之间找到最短的“友谊路径”很简单，但如果我们想找到一条不涉及特定友谊关系（或特定友谊关系集合）的最短友谊路径，而不先修改数据库呢？比如说，我们想找到从bob到joe的最短友谊路径，假设bob和joe自己并不是朋友，alice和janet也不是。

Answer 1

你能不能在Cypher中使用'allShortestPaths'这个选项，然后用Python来排除一些特定的关系类型或节点类型的路径呢？我想这要看你想用什么参数来限制结果，以及这些限制是否能仅通过Cypher返回给Python的路径来检测。

另一种方法是让Cypher返回从一个节点到另一个节点的所有可能路径（在查询中可以应用一些智能的限制）。

然后，基于Cypher返回的路径集合，你可以运行一些Python代码，排除那些包含你不感兴趣的特定关系类型或节点类型的路径。这样，你就会得到一组符合你接受标准的路径（除了最短路径的条件）。接下来，你可以用Python简单地计算这些路径的长度，并选择最短的那条。

实际上，Cypher本身可以为所有路径返回路径的长度。这个问题之前已经有人问过，所以这里是相关的问题供你参考。那个问题的接受答案就是我所说的内容。