用python3实现迪杰斯特拉算法

迪杰斯特拉算法（Dijkstra's Algorithm）是一种用于解决带权图最短路径问题的算法。以下是用 Python 3 实现迪杰斯特拉算法的示例代码：

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 printSolution(self, dist):
        print("Vertex \t Distance from Source")
        for node in range(self.V):
            print(node, "\t", dist[node])
    
    def minDistance(self, dist, sptSet):
        min = sys.maxsize
        min_index = 0
        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
        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]
        
        self.printSolution(dist)

这个实现中，Graph 类中包含了三个方法：

- `__init__(self, vertices)`: 构造函数，初始化图的大小。
- `printSolution(self, dist)`: 打印最短路径结果。
- `dijkstra(self, src)`: 迪杰斯特拉算法的主要实现。

其中，`dijkstra` 方法的实现流程如下：

1. 初始化 dist 数组，将所有元素的值设为 sys.maxsize，表示到源点的距离为无穷大。
2. 将源点的 dist 值设置为 0。
3. 初始化 sptSet 数组，将所有元素的值设为 False，表示这些点还没有被遍历到。
4. 对于每一个节点，从未遍历的节点中找到距离源点最近的节点。
5. 将该节点标记为已遍历。
6. 遍历该节点的所有邻居节点，更新它们的 dist 值。
7. 重复步骤 4~6 直到所有的节点都被遍历完成。

以下是一个简单的使用示例：

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)

输出结果：

Vertex   Distance from Source
0         0
1         4
2         12
3         19
4         21
5         11
6         9
7         8
8         14