Python最小树dijkstra算法

Dijkstra算法用于找到带权图中的单源最短路径，也可以用于最小生成树的构建。下面是使用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 print_mst(self, parent):
        print("Edge \tWeight")
        for i in range(1, self.V):
            print(parent[i], "-", i, "\t", self.graph[i][parent[i]])

    def min_key(self, key, mst_set):
        min = sys.maxsize

        for v in range(self.V):
            if key[v] < min and not mst_set[v]:
                min = key[v]
                min_index = v

        return min_index

    def dijkstra(self, src):
        key = [sys.maxsize] * self.V
        parent = [None] * self.V
        key[src] = 0
        mst_set = [False] * self.V

        parent[src] = -1

        for cout in range(self.V):
            u = self.min_key(key, mst_set)
            mst_set[u] = True

            for v in range(self.V):
                if self.graph[u][v] > 0 and not mst_set[v] and key[v] > key[u] + self.graph[u][v]:
                    key[v] = key[u] + self.graph[u][v]
                    parent[v] = u

        return self.print_mst(parent)

这个实现与使用Dijkstra算法找到单源最短路径的实现类似，只是在更新距离时不仅考虑到起点到某个节点的距离，还需要考虑到这个节点到其邻居节点的距离。最后构建最小生成树时，输出的是每个节点的父节点和边的权重。