在具有循环节点的复杂数据结构中寻找最短路径

Question

以下是我存储在JSON中的数据结构示例：

{
    "alpha": {
        "node1": "echo",
        "node2": "bravo"
    },
    "bravo": {
        "node1": "alpha",
        "node2": "bravo",
        "node3": "charlie"
    },
    "charlie": {
        "node1": "bravo",
        "node2": "foxtrot"
    },
    "delta": {
        "node1": "alpha",
        "node2": "hotel"
    },
    "echo": {
        "node1": "golf",
        "node2": "delta"
    },
    "foxtrot": {
        "node1": "echo",
        "node2": "india",
        "node3": "delta"
    },
    "golf": {
        "node1": "hotel",
        "node2": "charlie"
    },
    "hotel": {
        "node1": "foxtrot",
        "node2": "india"
    },
    "india": {
        "node1": "charlie",
        "node2": "hotel"
    }
}

我正在寻找任何两个节点之间的最短路径。例如，从echo到hotel的最短路径是：echo-

如您所见，这些节点是循环的，可以无休止地遍历它们。我还应该注意，节点路径都是单向的。因此，使用上面相同的示例，从酒店返回回声的最短路径是：酒店-

这样的数据结构有名字吗？我知道循环违反了“树”的规则。这是图形遍历吗？

Answer 1

你要找的是图中的最短路径。看看这个：

http://networkx.github.io/documentation/latest/reference/algorithms.shortest_paths.html

Answer 2

您拥有的是一个邻接列表。尽管这样做比较干净（删除节点1、节点2使其成为一个简单的数组）：

{
    "alpha": [
        "echo",
        "bravo"
    ],
    "bravo": [
        "alpha",
        "bravo",
        "charlie"
    ],
    ...
    "india": [
        "charlie",
        "hotel"
    ]
}

没有给出权重/距离，所以你可以用BFS找到最短的路径。这里有一个实现。