graph={
       'A':['B','C'],
       'B':['A','C','D'],
       'C':['A','B','D','E'],
       'D':['B','C','E','F'],
       'E':['C','D'],
       'F':['D']}
def BFS(graph,s):
    '''非递归广度优先算法以及两点之间最短路'''
    if not s or  not graph:
        return None
    queue=[]
    queue.append(s)
    seen=set()
    seen.add(s)
    parent={s:None} #初始点的前一个节点
    while len(queue)>0:
        vertex=queue.pop(0)
        nodes=graph[vertex]
        for w in nodes:
            if w not in seen:
                queue.append(w)
                seen.add(w)
                parent[w]=vertex #遍历中初始点的前一个节点
        print(vertex)
    return parent
###调用最短路函数
parent=BFS(graph,'E')
v='B'
while v!=None:
    print(v)
    v=parent[v]
    
    
def DfS(graph,s):
    '''深度优先搜索'''
    if not s or not graph:
        return None
    queue=[]
    queue.append(s)
    seen=set()
    seen.add(s)
    while(len(s))>0:
        vertex=queue.pop()
        nodes=graph[vertex]
        for w in nodes:
            if w not in seen:
                queue.append(w)
                seen.add(w)
        print(vertex)
        
        
'''dijkstra算法'''        
graph1={
       '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}
       }
import heapq
import math

def init_distance(graph,s):
    distance={s:0}
    for vertex in graph:
        if vertex != s:
            distance[vertex]=math.inf
    return distance

def dijkstra(graph,s):
    pqueue=[]
    heapq.heappush(pqueue,(0,s))
    seen=set()
    parent={s:None}
    distance=init_distance(graph,s)
    
    while len(pqueue)>0:
        pair=heapq.heappop(pqueue)
        dist=pair[0]
        vertex=pair[1]
        seen.add(vertex)
        nodes=graph[vertex].keys()
        for w in nodes:
            if w not in seen:
                if dist+graph[vertex][w]<distance[w]:
                    heapq.heappush(pqueue,(dist+graph[vertex][w],w))
                    parent[w]=vertex
                    distance[w]=dist+graph[vertex][w]
        return parent,distance
parent,distance=dijkstra(graph1,'A')
print(parent)
print(distance)