采用图的邻接矩阵或邻接表实现最短路径问题中的存储python

在Python中，使用图的数据结构（如邻接矩阵或邻接表）来解决最短路径问题（如Dijkstra算法或Bellman-Ford算法）时，我们需要首先定义图的表示：

1. **邻接矩阵**：
邻接矩阵是一个二维数组，其中行代表起点，列表示终点，值通常为边的权重（如果有权重）。如果两个顶点之间存在边，则对应位置的值为非零；若不存在，则为0。例如：

   graph_matrix = {
       'A': {'B': 5, 'C': 1},
       'B': {'A': 5, 'C': 2, 'D': 1},
       'C': {'A': 1, 'B': 2, 'D': 4},
       'D': {'B': 1, 'C': 4}
   }

对于查找最短路径，可以遍历矩阵寻找从源节点到目标节点的最小权重。

2. **邻接表**：
邻接表则是一个字典，每个节点作为键，其对应的值是一个列表，包含该节点的所有邻居及其权重。例如：

   graph_adjacency_list = {
       'A': [('B', 5), ('C', 1)],
       'B': [('A', 5), ('C', 2), ('D', 1)],
       'C': [('A', 1), ('B', 2), ('D', 4)],
       'D': [('B', 1), ('C', 4)]
   }

使用邻接表，查找路径时通常需要遍历每个节点的邻居，直到找到目标节点。

为了找出最短路径，你需要实现搜索算法（如优先队列辅助的Dijkstra或循环检测的Bellman-Ford），并记录每个节点的最低到达成本。