python贪心算法寻路

贪心算法是一种常用的算法思想，它在每一步选择中都采取当前状态下最优的选择，从而希望最终能够达到全局最优解。下面是一个使用贪心算法寻路的Python示例：

# 定义一个图的类
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, visited):
        min_dist = float('inf')
        min_index = -1
        for v in range(self.V):
            if dist[v] < min_dist and not visited[v]:
                min_dist = dist[v]
                min_index = v
        return min_index

    # 使用贪心算法寻找最短路径
    def dijkstra(self, src):
        dist = [float('inf')] * self.V
        dist[src] = 0
        visited = [False] * self.V

        for _ in range(self.V):
            u = self.min_distance(dist, visited)
            visited[u] = True

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

        return 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]]

# 打印最短路径
print("最短路径：", g.dijkstra(0))

这段代码实现了Dijkstra算法，通过贪心策略找到了从源点到其他顶点的最短路径。具体步骤如下：
1. 创建一个图的实例，其中包含顶点数和邻接矩阵。
2. 定义一个`min_distance`函数，用于找到距离最小的顶点。
3. 定义`dijkstra`函数，初始化距离数组`dist`和访问数组`visited`，将源点的距离设为0。
4. 循环遍历所有顶点，每次选择距离最小且未访问过的顶点作为当前顶点。
5. 更新当前顶点的邻接顶点的距离，如果新的距离更小，则更新距离数组`dist`。
6. 返回最短路径数组`dist`。