Python中的图(Graph)数据结构与最短路径算法

在Python中，可以使用多种数据结构来表示图，其中最常用的是邻接矩阵和邻接列表。邻接矩阵是一个二维矩阵，其中矩阵的元素表示图中两个节点之间的边的权重。邻接列表是一个字典，其中每个节点都关联一个列表，列表中的元素表示与该节点相邻的节点。

下面是一个使用邻接矩阵表示图的例子：

class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.matrix = [[0] * num_vertices for _ in range(num_vertices)]

    def add_edge(self, v1, v2, weight):
        self.matrix[v1][v2] = weight
        self.matrix[v2][v1] = weight

    def get_weight(self, v1, v2):
        return self.matrix[v1][v2]

    def get_adjacent_vertices(self, v):
        adjacent_vertices = []
        for i in range(self.num_vertices):
            if self.matrix[v][i] > 0:
                adjacent_vertices.append(i)
        return adjacent_vertices

    def __repr__(self):
        return str(self.matrix)

使用上述图数据结构，我们可以实现最短路径算法，其中最常用的是Dijkstra算法。Dijkstra算法用于找到图中两个节点之间的最短路径，并返回最小权重值。下面是一个使用Dijkstra算法找到最短路径的例子：

import heapq

def dijkstra(graph, start_vertex):
    distances = {v: float('infinity') for v in range(graph.num_vertices)}
    distances[start_vertex] = 0
    pq = [(0, start_vertex)]

    while pq:
        current_distance, current_vertex = heapq.heappop(pq)

        if current_distance > distances[current_vertex]:
            continue

        for neighbor in graph.get_adjacent_vertices(current_vertex):
            weight = graph.get_weight(current_vertex, neighbor)
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

# 创建一个图并添加边
g = Graph(9)
g.add_edge(0, 1, 4)
g.add_edge(0, 7, 8)
g.add_edge(1, 2, 8)
g.add_edge(1, 7, 11)
g.add_edge(2, 3, 7)
g.add_edge(2, 8, 2)
g.add_edge(2, 5, 4)
g.add_edge(3, 4, 9)
g.add_edge(3, 5, 14)
g.add_edge(4, 5, 10)
g.add_edge(5, 6, 2)
g.add_edge(6, 7, 1)
g.add_edge(6, 8, 6)
g.add_edge(7, 8, 7)

distances = dijkstra(g, 0)
print(distances)

在上述代码中，我们使用了Python标准库中的heapq模块来实现一个最小堆(priority queue)来帮助我们选择下一个距离最小的节点进行处理。

执行以上代码，将打印出从节点0到其他节点的最短路径的权重值。

以上就是Python中用于表示图和实现最短路径算法的示例。通过使用这些数据结构和算法，我们可以在不同的应用中解决如最短路径问题等类似的问题。