编写一个迪杰斯特拉算法

迪杰斯特拉算法是一种用于计算图中最短路径的算法，可以用于解决许多实际问题，比如路由选择、网络流量管理等。下面给出一个 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 min_distance(self, dist, sptSet):
        min_dist = sys.maxsize
        min_index = 0
        for v in range(self.V):
            if dist[v] < min_dist and sptSet[v] == False:
                min_dist = dist[v]
                min_index = v
        return min_index

    def dijkstra(self, src):
        dist = [sys.maxsize] * self.V
        dist[src] = 0
        sptSet = [False] * self.V

        for cout in range(self.V):
            u = self.min_distance(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]

        return dist

这个实现使用了一个 Graph 类来表示图。在构造函数中，我们初始化了一个二维数组来表示图的邻接矩阵。min_distance 方法用来找到距离当前节点最近的未标记节点。dijkstra 方法用来计算从源节点到所有其他节点的最短路径。我们首先将源节点的距离初始化为 0，将所有其他节点的距离初始化为无穷大。然后，我们在图中找到一个未标记的节点，它的距离最小，将其标记为已访问。然后，我们遍历该节点的所有邻居节点，如果该邻居节点还未被标记，并且从源节点到该邻居节点的距离比当前记录的距离更短，则更新该邻居节点的距离。

# 使用示例
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]]

print("最短路径：")
for i in range(9):
    print(f"从源节点到{i}的距离为{g.dijkstra(0)[i]}")

这个示例使用了一个包含 9 个节点的图来演示如何使用迪杰斯特拉算法计算最短路径。我们可以看到，对于从源节点（节点 0）到其他节点的最短路径已经被计算出来了。