用邻接矩阵表示图

Question

# Creating the graph as an adjacency matrix
vertices = [[0, 1, 1, 0],
            [0, 0, 1, 0],
            [0, 0, 0, 1],
            [0, 0, 0, 0]]
edges =  [[0, 3, 4, 0],
          [0, 0, 0.5, 0],
          [0, 0, 0, 1],
          [0, 0, 0, 0]]

所以我试图理解 python 中的 Dijkstra 算法，但我没有清楚地理解图表，因为我不理解每个子列表的真正含义，我理解某些数字，如 3、4 , 1 和 0.5 是某些 vericle 的距离，但仅此而已。我附上了图表在视觉上的样子。

Answer 1

邻接矩阵显示顶点对之间的信息。在此示例中，您应该将列表解释为矩阵，其中每行和每列中的元素对应于一对顶点：

这里，a列和a行，或者位置(0, 0)处的0表示从a节点到a 节点和 b 列和 a 行或位置 (0, 1) 中的 1 表示从 a 节点到 b节点。换句话说，凡是有1的地方，就表示有一条边从行对应的节点开始，到列对应的节点结束，而0则表示没有边。

对edges列表应用类似的逻辑，它标记边的权重而不是仅仅标记边是否存在。正如@misha 提到的，此列表不足以表示节点的互连性，因为节点之间的边可能具有 0 的权重，这与根本不存在的边无法区分，因此 edges 和vertices 需要矩阵

用邻接矩阵表示图

Representing a graph with an adjacency matrix

python

dijkstra

python-3.x