python - 如何通过python中的A *寻路算法运行三维列表

我是一个正在（尝试）编写一个python实现a*算法的学生我知道这个问题已经被问过100次了，但是我对我的情况有一些细节还没有完全理解。
我有一个带10个节点的加权无向图我的实际图形将有更多的节点。该图按三维列表排序。我正在粘贴我们为生成图形而编写的程序的一些输出。

Node 1 : [[8, 3], [9, 11], [2, 12], [3, 12], [7, 6]]
Node 2 : [[5, 6], [4, 3], [1, 12], [8, 11], [7, 1]]
Node 3 : [[6, 2], [1, 12], [5, 7], [9, 1]]
Node 4 : [[2, 3], [8, 2], [10, 5], [5, 10], [7, 4]]
Node 5 : [[2, 6], [4, 10], [3, 7], [7, 8]]
Node 6 : [[3, 2], [9, 10]]
Node 7 : [[2, 1], [4, 4], [5, 8], [1, 6], [8, 3]]
Node 8 : [[1, 3], [2, 11], [4, 2], [7, 3], [10, 4]]
Node 9 : [[1, 11], [6, 10], [3, 1]]
Node 10 : [[4, 5], [8, 4]]

在可读性较差的格式中，图形存储为三维列表例如，在索引0处，有到节点8、9、2、3和7的连接节点8和0之间的权重为3。节点0到9和11之间的权重我想你明白了。

myGraph = [[[8, 3], [9, 11], [2, 12], [3, 12], [7, 6]], [[5, 6], [4, 3], [1, 12], [8, 11], [7, 1]], [[6, 2], [1, 12], [5, 7], [9, 1]], [[2, 3], [8, 2], [10, 5], [5, 10], [7, 4]], [[2, 6], [4, 10], [3, 7], [7, 8]], [[3, 2], [9, 10]], [[2, 1], [4, 4], [5, 8], [1, 6], [8, 3]], [[1, 3], [2, 11], [4, 2], [7, 3], [10, 4]], [[1, 11], [6, 10], [3, 1]], [[4, 5], [8, 4]]]

所以现在的挑战是找到一个python的a*实现，它将接受一个列表作为输入，并输出最佳路径。似乎大多数图都是围绕字典数据类型构建的，但这不是我的情况。
我已经开始尝试用3d列表来编写我自己的a*版本，但是运气不好，因为它对我来说有点复杂。

最佳答案

下面是未经测试的伪代码，为@luai ghunim所说的添加细节。
首先，您可以在python标准库中找到优先级队列实现https://docs.python.org/3/library/heapq.html。它将存储您的todo列表。
第二，排队的东西需要很好地分类。一个技巧是使用元组，其中第一个字段是您希望排序的字段。这样地：

[estimated_total, node, cost]

您可以使用https://docs.python.org/3/library/collections.html#collections.namedtuple为字段命名，使它们看起来很漂亮。假设你没有，但这是个人的选择。
第三，需要有一个函数来估计从任何节点到终点的距离。我们称之为estimator(node)。
最后，我们需要一个字典，名为from_node，说明如何到达一个特定的节点它的条目看起来像：

node: {"from": prev_node, "cost": 6}

考虑到这一点，它应该像这样工作：

# Start with node 0 in our lookup.
from_node = {0: {"from_node": None, "cost": 0.0}}
# And in our todo.
todo = [[estimator(0), 0, 0.0]]
while 0 < len(todo):
    (estimated_cost, node, cost) = heapq.heappop(todo)
    if cost == from_node[node]["cost"]:
        if node == target_node:
            # We have our answer and know that it is best.
            break
        else:
            for (next_node, next_cost) in my_graph[node]:
                total_cost = cost + next_cost
                if next_node in from_node:
                    if from_node[next_node]["cost"] <= total_cost:
                        # We have a better path.
                        continue
                from_node[next_node] = {"from": node, "cost": total_cost}
                heapq.heappush(todo,
                    [total_cost + estimator(next_node), next_node, total_cost])
if target_node in from_node:
    reversed_path = []
    node = target_node
    while node is not None:
        reversed_path.append(node)
        node = from_node[node]["from"]
    # AND NOW reversed(reversed_path) IS YOUR ANSWER
else:
    # THERE IS NO ANSWER