在Python中找到图中所有顶点中最小成本的和的程序

在图论中，我们常常需要找到一些图上的最短路径或者最小权值之类的问题。其中较为常见的就是求解“所有顶点中最小成本的和”的问题。本文将为读者介绍如何在Python中，通过Dijkstra算法，实现这一问题的求解。

Dijkstra算法

Dijkstra算法是一种基于贪心策略的单源最短路径算法，它的基本思路是从起点开始，依次扩展到离该点最近的一个点，再依次依此扩展到离该点最近的一个点，以此类推，一直到扩展到终点为止。

在Dijkstra算法中，使用一个数组dist表示从起点到各个点的最短距离，使用一个集合s表示已经找到其最短距离的点集，初始时将起点加入到集合s中，并将dist数组中除了起点节点外的所有节点的距离设置为无穷大。每次从未标记点中选取到起点距离最近的一个点，更新以它为起点的所有边的终点节点的dist数组。重复以上操作直至找到终点，或未找到满足条件的路径。

实现

在Python中，我们可以使用邻接矩阵或者邻接表来表示一个图。下面的示例中，我们使用邻接矩阵表示图。

import heapq

def dijkstra(graph, start, end):
    heap = [(0, start)]
    visited = set()
    dist = {start: 0}
    while heap:
        (cost, node) = heapq.heappop(heap)
        if node in visited:
            continue
        visited.add(node)
        if node == end:
            return dist[node]
        for neighbor in range(len(graph[node])):
            if graph[node][neighbor] == 0:
                continue
            elif neighbor in visited:
                continue
            new_cost = cost + graph[node][neighbor]
            if neighbor not in dist or new_cost < dist[neighbor]:
                dist[neighbor] = new_cost
                heapq.heappush(heap, (new_cost, neighbor))

    return None

if __name__ == "__main__":
    INF = float('inf')
    graph = [[0, 1, 12, INF, INF, INF], [1, 0, 9, 3, INF, INF], [12, 9, 0, 6, 10, INF], [INF, 3, 6, 0, 2, 7], [INF, INF, 10, 2, 0, 4], [INF, INF, INF, 7, 4, 0]]
    start = 0
    end = 5
    print(dijkstra(graph, start, end))

在上述代码中，我们使用heapq库中提供的堆数据结构来进行维护。具体来说，heapq.heappop()方法可以弹出堆中的第一个元素（即“未访问”节点中离起点最近的节点），heapq.heappush()方法可以把一个元素插入到堆中并保持堆的有序性。