import math class Graph(): def __init__(self, vertices): self.V = vertices self.graph = [[0 for col in range(vertices)] for row in range(vertices)] def printSolution(self, dist): print("Vertex \t Distance from Source") for node in range(self.V): print(node, "\t\t", dist[node]) def minDistance(self, dist, sptSet): min = 1e7 for v in range(self.V): if dist[v] < min and sptSet[v] == False: min = dist[v] min_index = v return min_index def dijkstra(self, src): dist = [1e7] * self.V dist[src] = 0 sptSet = [False] * self.V for count in range(self.V): u = self.minDistance(dist, sptSet) sptSet[u] = True for v in range(self.V): if (self.graph[u][v] > 0 and sptSet[v] == False and dist[v] > dist[u] + self.graph[u][v]): dist[v] = dist[u] + self.graph[u][v] self.printSolution(dist) g = Graph(9) g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0], [4, 0, 8, 0, 0, 0, 0, 11, 0], [0, 8, 0, 7, 0, 4, 0, 0, 2], [0, 0, 7, 0, 9, 14, 0, 0, 0], [0, 0, 0, 9, 0, 10, 0, 0, 0], [0, 0, 4, 14, 10, 0, 2, 0, 0], [0, 0, 0, 0, 0, 2, 0, 1, 6], [8, 11, 0, 0, 0, 0, 1, 0, 7], [0, 0, 2, 0, 0, 0, 6, 7, 0] ] g.dijkstra(0)

这是一个实现 Dijkstra 算法的代码。Dijkstra 算法是用于求解有权图中单个源点到其他所有顶点的最短路径的算法。在这段代码中，Graph 类中的 graph 属性表示了有向图的邻接矩阵，printSolution 方法用于打印每个顶点到源点的最短距离，minDistance 方法用于找到距离源点最近的未访问顶点，dijkstra 方法用于计算源点到其他所有顶点的最短路径。在这段代码中，给定的有向图是一个 9 个顶点的图，每个顶点之间的边有对应的权重，源点是 0。代码的输出是每个顶点到源点的最短距离。

相关问题

解释这段代码class Graph: def __init__(self, num_vertices): self.num_vertices = num_vertices self.adj_list = [[] for _ in range(num_vertices)] def add_edge(self, u, v): self.adj_list[u].append(v) self.adj_list[v].append(u)

这段代码定义了一个名为Graph的类，它表示一个无向图。构造函数__init__接收参数num_vertices，表示图中节点的数量，然后初始化一个大小为num_vertices的空邻接表adj_list。邻接表是一个列表，其中包含了每个节点的邻居节点。每个邻居列表初始化为空列表[]。

add_edge方法用于向图中添加一条边。它接受两个参数u和v，表示两个节点之间存在一条边。它将v添加到u的邻居列表中，并将u添加到v的邻居列表中，因为这是一个无向图，边是双向的。

例如，如果我们要创建一个包含4个节点的无向图，可以这样做：

g = Graph(4)
g.add_edge(0, 1)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(3, 0)

这将创建一个环形图，其中每个节点都与相邻的两个节点相连。

按照如下定义给G=Graph()添加边举例子class Graph: def __init__(self): self.vertices = {} self.numVertices = 0 # 初始图 顶点0 def addVertex(self, key): # add顶点 self.numVertices = self.numVertices + 1 newVertex = Vertex(key) self.vertices[key] = newVertex # 顶点对应属性 return newVertex def getVertex(self, key): if key in self.vertices: return self.vertices[key] else: return None def __contains__(self, key): # check判断是否存在 return key in self.vertices def addEdge(self, f, t, cost): # 添加边 if f not in self.vertices: nv = self.addVertex(f) # 顶点未在图的顶点集先加入 if t not in self.vertices: nv = self.addVertex(t) self.vertices[f].addNeighbor(self.vertices[t], cost) # 添加邻接点

好的，假设我们要给这个图添加一条从顶点0到顶点1的边，边权为2，代码如下：

G = Graph()
G.addVertex(0)
G.addVertex(1)
G.addEdge(0, 1, 2)

这样就在图中添加了一条从顶点0到顶点1的边，边权为2。