prim算法和dijkstra算法

Prim算法和Dijkstra算法是两种常用的图算法，用于解决不同的问题。

1. Prim算法：
Prim算法是一种用于构建最小生成树的贪心算法。它从一个起始顶点开始，逐步扩展最小生成树的边，直到包含所有顶点为止。具体步骤如下：
- 选择一个起始顶点作为最小生成树的根节点。
- 从根节点开始，选择与当前最小生成树相连的边中权值最小的边，并将其加入最小生成树。
- 重复上一步，直到最小生成树包含所有顶点。
2. Dijkstra算法：
Dijkstra算法是一种用于求解单源最短路径的算法。它可以计算出从一个起始顶点到其他所有顶点的最短路径。具体步骤如下：
- 初始化起始顶点的最短路径为0，其他顶点的最短路径为无穷大。
- 选择一个未访问的顶点中最短路径最小的顶点作为当前顶点。
- 更新当前顶点相邻顶点的最短路径，如果经过当前顶点到达相邻顶点的路径比已知的最短路径更短，则更新最短路径。
- 重复上一步，直到所有顶点都被访问。

下面是一个使用Prim算法和Dijkstra算法的示例代码：

# Prim算法
def prim(graph, start):
    visited = set()
    min_span_tree = []
    visited.add(start)
    while len(visited) < len(graph):
        min_edge = None
        for u in visited:
            for v in graph[u]:
                if v[0] not in visited and (min_edge is None or v[1] < min_edge[1]):
                    min_edge = (v[0], v[1], u)
        min_span_tree.append(min_edge)
        visited.add(min_edge[0])
    return min_span_tree

# Dijkstra算法
def dijkstra(graph, start):
    distances = {v: float('inf') for v in graph}
    distances[start] = 0
    visited = set()
    while len(visited) < len(graph):
        min_distance = float('inf')
        min_vertex = None
        for v in graph:
            if v not in visited and distances[v] < min_distance:
                min_distance = distances[v]
                min_vertex = v
        visited.add(min_vertex)
        for neighbor, weight in graph[min_vertex]:
            if distances[min_vertex] + weight < distances[neighbor]:
                distances[neighbor] = distances[min_vertex] + weight
    return distances

# 示例图
graph = {
    'A': [('B', 5), ('C', 1)],
    'B': [('A', 5), ('C', 2), ('D', 1)],
    'C': [('A', 1), ('B', 2), ('D', 4), ('E', 8)],
    'D': [('B', 1), ('C', 4), ('E', 3), ('F', 6)],
    'E': [('C', 8), ('D', 3)],
    'F': [('D', 6)]
}

# 使用Prim算法构建最小生成树
min_span_tree = prim(graph, 'A')
print("Prim算法最小生成树：", min_span_tree)

# 使用Dijkstra算法求解单源最短路径
distances = dijkstra(graph, 'A')
print("Dijkstra算法最短路径：", distances)