迪杰斯特拉（Dijkstra）算法 python2.7

# coding=utf-8
# This is a sample Python script.
# Press Shift+F10 to execute it or replace it with your code.
# Press Double Shift to search everywhere for classes, files, tool windows, actions, and settings.
# Definition for singly-linked list.
#建立有向无环图
graph={}
graph['music']={}
graph['music']['poster']=0
graph['music']['vinyl']=5
graph['poster']={}
graph['poster']['guitar']=30
graph['poster']['drum']=35
graph['vinyl']={}
graph['vinyl']['drum']=20
graph['vinyl']['guitar']=15
graph['guitar']={}
graph['guitar']['piano']=20
graph['drum']={}
graph['drum']['piano']=10
graph['piano']={}
def Dijkistra(start,end):
    """

    :param start:
    :param end:
    :return:
    costTF:花费列表，元素包含4个信息[0]：本顶点；[1]：目前start到本顶点的最少花费；[2]：是否已更新；[3]：目前最少花费的上个顶点
    sign：为了遍历一次然后看是否全部置True的标志sign==True即为递归出口
    index_：未更新的最小权值点（即本次将要置T的点）在costTF中的索引
    guard：遍历目前的costTF并且返回表中花费最小的顶点名[0]和权值[1]
    list_re：返回列表，记录start到end所有的顶点
    """
    costTF = [[start, 0,False, None]]
    def UpdateVex():
        #从F中找到最小权值顶点vex，置T，更新顶点的邻居的花费，直到没有F的顶点,costTF
        guard=['',float('inf')]
        index_=-1
        sign=True
        for parent_vex in range(len(costTF)):#遍历表找到没有更新的最小权值顶点guard
            if costTF[parent_vex][2]==False:#找到花费最小的顶点
                if guard[1]>costTF[parent_vex][1]:
                    guard=costTF[parent_vex][0],costTF[parent_vex][1]#这是不是有别的写法？
                    index_=parent_vex#index_就是当前点
                    sign=False
                else:
                    pass
            else:
                pass
        if sign==True:#全部置True，但是这里return可能是全是T也可能是F
            return #TODO 递归出口
        else:#TODO 没到出口就更新完继续递归
            costTF[index_][2]=True
            if graph[guard[0]]=={}:
                pass
            else:
                for neighbor in graph[guard[0]]:#去图中取邻居,这里没进去
                    list_temp=[ i[0] for i in costTF ]
                    if neighbor in list_temp:#如果邻居在表中（且Flase），更新权值，更新父顶点
                        index_temp=list_temp.index(neighbor)
                        if costTF[index_temp][2]==False:#Flase
                            if graph[guard[0]][neighbor]+costTF[index_][1] 
明天再理顺一下，太晚了
 
list_temp=[ i[0] for i in costTF ]二维数组只取第一个元素组成新的列表。
 
注意表的元素，如果是{['guitar',0]，['music'，1]}这种二维数组，'guitar'是不在表里的