利用迪杰斯特拉算法构建无向图并在此基础上求得指定起点和终点的最短路径

迪杰斯特拉算法是一种用于求解单源点最短路径的算法。它可以用来构建无向图，并找到指定起点和终点之间的最短路径。下面是一个示例代码，演示了如何使用迪杰斯特拉算法来实现这个功能：

import sys

# 构建无向图
def build_graph(edges):
    graph = {}
    for edge in edges:
        u, v, weight = edge
        if u not in graph:
            graph[u] = {}
        if v not in graph:
            graph[v] = {}
        graph[u][v] = weight
        graph[v][u] = weight
    return graph

# 迪杰斯特拉算法
def dijkstra(graph, start, end):
    # 初始化距离字典和前驱节点字典
    distances = {node: sys.maxsize for node in graph}
    distances[start] = 0
    predecessors = {}

    # 记录已经访问过的节点
    visited = set()

    # 循环找到最短路径
    while len(visited) < len(graph):
        # 找到当前距离最小的节点
        min_distance = sys.maxsize
        min_node = None
        for node in graph:
            if node not in visited and distances[node] < min_distance:
                min_distance = distances[node]
                min_node = node

        # 标记该节点为已访问
        visited.add(min_node)

        # 更新与该节点相邻节点的距离
        for neighbor in graph[min_node]:
            new_distance = distances[min_node] + graph[min_node][neighbor]
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                predecessors[neighbor] = min_node

    # 构建最短路径
    path = []
    node = end
    while node != start:
        path.insert(0, node)
        node = predecessors[node]
    path.insert(0, start)

    return path

# 示例数据
edges = [('A', 'B', 4), ('A', 'C', 2), ('B', 'C', 1), ('B', 'D', 5), ('C', 'D', 8), ('C', 'E', 10), ('D', 'E', 2), ('D', 'F', 6), ('E', 'F', 3)]
start = 'A'
end = 'F'

# 构建图并求最短路径
graph = build_graph(edges)
shortest_path = dijkstra(graph, start, end)
print("Shortest path from", start, "to", end, ":", shortest_path)

这段代码首先定义了一个`build_graph`函数，用于构建无向图。然后定义了一个`dijkstra`函数，用于实现迪杰斯特拉算法。最后，给出了一个示例数据，并调用`build_graph`和`dijkstra`函数来构建图并求解最短路径。运行代码后，将输出从起点到终点的最短路径。