堆优化的Dijkstra算法用PYTHON实现

戴克斯特拉算法（Dijkstra’s algorithm）是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。 该算法的输入包含了一个有权重的有向图 G，以及G中的一个来源顶点 S。我们以 V 表示 G 中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。(u, v) 表示从顶点 u 到 v 有路径相连。我们以 E 表示G中所有边的集合，而边的权重则由权重函数 w: E → [0, ∞] 定义。因此，w(u, v) 就是从顶点 u 到顶点 v 的非负权重（weight）。边的权重可以想像成两个顶点之间的距离。任两点间路径的权重，就是该路径上所有边的权重总和。已知有 V 中有顶点 s 及 t，Dijkstra 算法可以找到 s 到 t的最低权重路径(例如，最短路径)。这个算法也可以在一个图中，找到从一个顶点 s 到任何其他顶点的最短路径。对于不含负权的有向图，Dijkstra算法是目前已知的最快的单源最短路径算法。

import time
import heapq

def dijkstra（Gstart）:     ###dijkstra算法    
    INF = 999999999

    dis = dict（（keyINF） for key in G）    # start到每个点的距离
    dis[start] = 0
    vis = dict（（keyFalse） for key in G）    #是否访问过，1位访问过，0为未访问
    ###堆优化
    pq = []    #存放排序后的值
    heapq.heappush（pq[dis[start]start]）

    t3 = time.time（）
    path = dict（（key[start]） for key in G）    #记录到每个点的路径
    while len（pq）>0:
        v_disv = heapq.heappop（pq）    #未访问点中距离最小的点和对应的距离
        if vis[v] == True:
            continue
        vis[v] = True
        p = path[v].copy（）    #到v的最短路径
        for node in G[v]:    #与v直接相连的点
            new_dis = dis[v] + float（G[v][node]）
            if