假设命题：对于所有已探寻的结点v，通过Dijkstra贪心策略所找出的贪心路径长度 B[v] 为从A到V节点的真正最短路 S[A->V] 也就是B[v]=S[A->V]。

1）第一次运行的情况：A结点，B[A]=0, S[A->A]=0, 在没有负权边情况下显然满足
2）假设第k-1次运行已经成立，那么对第k次运行，我们只需证明，对于Dijkstra所加入的新结点w*，没有更短的从A通向w* 的路径：

假设P为从A通向w*（Dijkstra所找到的新结点） 的任意一条路径，那么P内至少包含一条桥梁边（需要穿越旧大陆到新大陆至少一次），我们假设第一次实现穿越的边为（y，z），y属于{X}（旧大陆），z属于{V-X}（新大陆）。我们便可以将P拆分为：
	P(A->Y)+P(Y->Z)+P(Z->W)
1 根据归纳假设，b[y]是A到y的最短路径，那么p路径中从S到达Y的距离必然不会超过此前计算的从A到Y的最短路B[y]：
	P（A->Y）> S(A->Y)=B[y]
2 根据Dijkstra贪心策略，我们选取的w* 永远满足：B[v*]+l[v*->w*] 是所有通过桥梁边实现穿越的路径中最小的，那么；
	B[v*]+l[v*->w*]<=B[y]+l[y->z]
3  又因为没有负权边，因而总有 B[z->w]>=0
4 整合后得到不等式：
	P（A->w）=P(A->Y)+P(Y->Z)+P(Z->w)>=B[y]+l[y->z]>=B[v*]+l[v*->w*]
	也就是在无负权边的情况下，任意P路径长度都不会比Dijkstra贪心策略得到的结果小。
根据数学归纳法，原假设成立。

import heapq 
import random

#我们使用random生成10个随机元素，然后把它们扔进堆里
h = [random.randint(1, 100) for _ in range(10)] 
print("随机生成的数列：", h) 

heapq.heapify(h) 
print("转换为最小堆后的数列：", h) 

#查询最小值
min = heapq.heappop(h) 
print("弹出的最小元素：", min) 
print("剩余的堆元素：", h) 

# 向堆中插入一个新的随机数字 
x = random.randint(1, 100) 
heapq.heappush(h, x) 
print("插入新元素后的堆：", h) 

随机生成的数列： [52, 14, 11, 78, 86, 44, 47, 42, 76, 8]
转换为最小堆后的数列： [8, 14, 11, 42, 52, 44, 47, 78, 76, 86]
弹出的最小元素： 8
剩余的堆元素： [11, 14, 44, 42, 52, 86, 47, 78, 76]
插入新元素后的堆： [11, 14, 44, 42, 51, 86, 47, 78, 76, 52]

heap = []
heapq.heappush(heap, new_element)

import heapq

  
class Graph: #建立Graph类储存边和结点

    def __init__(self):

        self.nodes = set() # initializing a set to store the node code

        self.edges = {} # initializing edge as empty dictionary
        

    def add_node(self, value):

        self.nodes.add(value) # constructing nodes according to the starting and ending point of edge 

        if value not in self.edges:

            self.edges[value] = {}


    def add_edge(self, from_node, to_node, weight):

        self.add_node(from_node)

        self.add_node(to_node)

        self.edges[from_node][to_node] = weight 
        # Supposing we are dealing with direct graph  在这里采用了有向图，但是Dijkstra也可以处理无向图      

    def dijkstra(self, start):

        distances = {node: float('inf') for node in self.nodes} 
        #initializing the shortest distance as infinite 

        distances[start] = 0 #我们用distance数组记录从原点到每一个点的最短路，原点到原点则记为0

        heap = [(0, start)] #用堆来记录当前所有备选桥梁路径长度（从新大陆到旧大陆的穿越路径）

        while heap:

            current_distance, current_node = heapq.heappop(heap) #每次将堆顶的结点移出，由于堆顶元素总是最小，此处一步实现将最短路径加入旧大陆的贪心过程。注意，由于堆内使用的是元组（tuple），默认按照第一个元素维护堆。

			for neighbor, weight in self.edges[current_node].items(): 
			#枚举和此时堆顶结点相连的所有边,若尚未在桥梁边中或到达当前邻居的最短路刷新，则将他们加入/再次更新桥梁边合集。
                distance = current_distance + weight
                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    heapq.heappush(heap, (distance, neighbor)) 

        return distances