python - 找到排除特定边缘的最短路径？

Question

我正在使用 Py2neo，但这可能并不重要，因为这很可能需要通过编写 Cypher 查询来完成。

本质上，我想在子图中找到一条最短路径，其中子图占整个图的大部分，但删除了很小一部分(百万分之一或更少)的边。

例如，假设我有节点 A、B 和 C，以及边 (A->B)、(A->C)、(B->C)。当然，从 A 到 C 的最短路径是通过直接连接。但是，如果我想找到不使用该边的最短路径，则必须是 A B C。

此外，这将是用户可以在多用户(网络)应用程序中指定的内容。所以我不能真正改变数据库本身......如果这不是问题，我也许可以在边上创建一个属性“允许:真/假”并将其设置为假，但这会扰乱应用程序的行为所有当前用户。

对此的一种变体是“不允许:sessionID1、sessionID230、sessionID1010”，即实际存储哪些应用程序 session 想要在边缘本身中排除该边缘，但这似乎也不理想。

当然，我实际上可以在 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

在任意两个人之间找到一条最短的“友谊路径”很容易，但是如果我们想找到一条不涉及特定友谊关系(或特定的一组关系)的最短友谊路径怎么办？ friendship rels)，但不先修改数据库？例如，我们想要找到从 bob 到 joe 的最短友谊路径，其中我们暂时假设 bob 和 joe 本身不是 friend ，alice 和 janet 也不是。

Answer 1

你不能使用'allShortestPaths吗？ ' 密码中的选项并使用它来拒绝包含某些特定 rel 类型或使用 python 的节点类型的路径？我想这将取决于您想要限制结果的方式和参数，以及是否可以仅使用以路径形式返回给 python 的密码来检测它们。

另一种方法是指示 Cypher 将所有可能的路径从一个节点返回到另一个节点(可以在此处的查询本身中应用一些智能限制)。

然后根据 Cypher 返回的路径集合，您可以运行一些 Python 代码来拒绝包含您不感兴趣的特定 rel 类型或节点类型的路径。然后您将得到一个集合符合您的接受标准的可能路径(最短条件除外)。然后，您可以使用 python 简单地计算路径的长度，并使用最小的。

其实对于所有的路径，Cypher自己都可以返回路径的长度。这已经被问过，所以here is the question供你引用。这个问题的公认答案就是我所说的。