dijsktra路径规划

### 关于Dijkstra算法在路径规划中的实现与应用

#### Dijkstra算法简介
Dijkstra算法由荷兰计算机科学家Edsger W. Dijkstra于1959年提出，用于计算加权图中从一个顶点到其他所有顶点的最短路径。该算法特别适用于具有非负权重边的情况，在地图导航、网络路由等领域有着广泛应用[^2]。

#### 算法核心思想
此算法的核心在于利用贪心策略逐步构建最短路径树。具体来说，就是从未处理过的节点集合中挑选离起点最近的一个作为当前节点，并更新其相邻节点的距离值；重复这一过程直至遍历完所有可达节点或到达目标位置。

#### Python代码示例
下面给出一段基于优先队列优化版本的Python代码来演示如何使用Dijkstra算法求解两点间最短路径：

import heapq

def dijkstra(graph, start):
    queue = []
    distances = {node: float('inf') for node in graph}
    predecessors = {node: None for node in graph}

    distances[start] = 0
    heapq.heappush(queue, (distances[start], start))

    while queue:
        current_distance, u = heapq.heappop(queue)

        if current_distance != distances[u]:
            continue
        
        for v, weight in graph[u].items():
            distance = current_distance + weight
            
            if distance < distances[v]:
                distances[v] = distance
                predecessors[v] = u
                heapq.heappush(queue, (distance, v))
    
    return distances, predecessors


# 测试用例
if __name__ == "__main__":
    G = {
        'A': {'B': 7, 'C': 9},
        'B': {'A': 7, 'F': 2},
        'C': {'A': 9, 'F': 6, 'G': 8},
        'F': {'B': 2, 'C': 6, 'G': 3},
        'G': {'C': 8, 'F': 3}
    }

    dist, prev = dijkstra(G, "A")

    print(f"Distance from A to each vertex:")
    for key in sorted(dist.keys()):
        path = ""
        end = key
        while end is not None:
            path += f"{end} <- "
            end = prev[end]

        print(f"\t{key}: {dist[key]} via [{path[:-4]}]")

这段程序定义了一个`dijkstra()`函数接收图形结构以及起始点参数并返回两个字典：一个是记录各个结点最小开销（即距离），另一个则是用来重建最优路线所需的前驱表。最后通过测试实例展示了如何调用上述功能完成简单的最短路查询任务[^1]。