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)
时间: 2024-04-22 22:21:38 浏览: 18
这是一个实现 Dijkstra 算法的代码。Dijkstra 算法是用于求解有权图中单个源点到其他所有顶点的最短路径的算法。在这段代码中,Graph 类中的 graph 属性表示了有向图的邻接矩阵,printSolution 方法用于打印每个顶点到源点的最短距离,minDistance 方法用于找到距离源点最近的未访问顶点,dijkstra 方法用于计算源点到其他所有顶点的最短路径。在这段代码中,给定的有向图是一个 9 个顶点的图,每个顶点之间的边有对应的权重,源点是 0。代码的输出是每个顶点到源点的最短距离。