迪杰斯特拉算法python实现并打印路径

以下是使用Dijkstra算法在Python中实现并打印路径的示例代码：

import sys

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for column in range(vertices)]
                      for row in range(vertices)]

    def printPath(self, parent, j):
        if parent[j] == -1:
            print(j, end=' ')
            return
        self.printPath(parent, parent[j])
        print(j, end=' ')

    def printSolution(self, dist, parent, src):
        print("Vertex \t Distance from Source \t Path")
        for node in range(self.V):
            print(node, "\t\t", dist[node], "\t\t", end='')
            self.printPath(parent, node)
            print()

    def minDistance(self, dist, sptSet):
        min = sys.maxsize

        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 = [sys.maxsize] * self.V
        parent = [-1] * self.V
        dist[src] = 0
        sptSet = [False] * self.V

        for cout 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]
                    parent[v] = u

        self.printSolution(dist, parent, src)

在上面的代码中，我们首先定义了一个`Graph`类，其中`__init__`方法初始化了`V`个节点的图。然后，`printPath`方法用于打印源节点到目标节点的最短路径。`printSolution`方法用于打印从源节点到每个节点的距离及其路径。`minDistance`方法用于找到距离源节点最近的未访问节点。最后，`dijkstra`方法使用Dijkstra算法找到从源节点到每个节点的最短路径，并打印结果。