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

这是我存储在 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 -> golf -> hotel

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

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

请您参考如下方法:

你有一个 adjacency list .虽然这样更干净(删除 node1、node2 使其成为一个简单的数组):

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

没有给出权重/距离，因此您可以使用 BFS 找到最短路径。 Here是一个实现。