表示具有邻接矩阵的图

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这样的数字是距离某些顶点，但事实并非如此。我要附上图形外观的图像。

Answer 1

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

  a b c d
a 0 1 1 0
b 0 0 1 0
c 0 0 0 1
d 0 0 0 0

这里，a列和a行中的0，或位置（0，0）表示从a节点到a节点没有边，而在b列中为1。 a列和a行或位置（0，1）表示从b节点到edges节点有一条边。换句话说，在任何地方有1的地方，都表示有一条边开始于与该行相对应的节点，并在与该列所对应的节点处结束，而0则表明没有一条边。]

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