有向带权图的单源最短路径经典算法是dijkstra，下面就对算法的过程和代码实现进行记录

 

算法过程：

1、数据结构：图的带权邻接矩阵G.Edge[u][i],如果u到i有边则G.Edge[u][i]等于<u,i>边的权值；否则G.Edge[u][i]等于∞。
一维数组dist[i]记录从起始点到i节点的最短路径长度，一维数组p[i]记录i节点最短路径的前驱
2、初始化：令集合S={u}，其中u是起始点，对于V-S集合所有顶点i，初始化dist[i]=G.Edge[u][i]，其中集合V是所有顶点的集合。如果i是u的邻接点，初始化p[i]=u,否则p[i]=-1
3、找最小：在集合V-S中按照贪心策略在dist中找出最小值dist[i],则顶点i就是离源点u最近的节点(注意：此处找到的最小i并不一定就是上一步找到节点的邻接点)
4、将找到的i节点加入到s集群，并更新V-S
5、判断是否结束：如果V-S为空则搜索结束，否则到步骤6
6、对结合V-S中与节点i邻接的顶点j,如果有dist[j]>dist[i]+G.Edge[i][j]则dist[j]=dist[i]+G.Edge[i][j]；更新p[j]=i,继续执行步骤3

 

代码实现：

#!/usr/bin/env python
# -*- coding:utf-8 -*-


graphNodeList = [] #图存储节点信息
graphAdjMatrix = [] #有向权重图邻接矩阵
searchNodeInfo = [] #djstla最短距离已经遍历的节点
dist = [] #存储最短路径开销
p = [] #djstla最短路径每个顶点的直接前驱
MAX = 100000



#str切分后给列表赋值格式
def acquireNode():
    node_list = input("请输入途中所有的点，以空格分隔：")
    for nodeInfo in node_list.strip().split(" "):
        graphNodeList.append(nodeInfo)

#根据输入信息填写邻接矩阵
def acquireSideUndig():
    print("请输入图的所有边信息，格式为边的两个顶点，使用空格分隔。 eg:a b,如果全部信息输入完毕请输入end")
    while True:
        tempSide = input(">:")
        if tempSide.strip().lower() == "end":
            print("输入结束")
            break
        tempNodeList = tempSide.strip().split(" ")
        if len(tempNodeList) == 2:
            if tempNodeList[0] in graphNodeList and tempNodeList[1] in graphNodeList:
                createUndigraphAdjMatrix(tempNodeList[0], tempNodeList[1])
            else:
                print("边信息输入有误，请重新输入")
            continue
        else:
            print("输入有误请重新输入")
            continue

def acquireSideDig():
    print("请输入图的所有边信息，格式为边的两个顶点，使用空格分隔。 eg:a b,如果全部信息输入完毕请输入end")
    while True:
        tempSide = input(">:")
        if tempSide.strip().lower() == "end":
            print("输入结束")
            break
        tempNodeList = tempSide.strip().split(" ")
        if len(tempNodeList) == 2:
            if tempNodeList[0] in graphNodeList and tempNodeList[1] in graphNodeList:
                createDigraphAdjMatrix(tempNodeList[0], tempNodeList[1])
            else:
                print("边信息输入有误，请重新输入")
            continue
        else:
            print("输入有误请重新输入")
            continue

def acquireSideDigWeight():
    print("请输入图的所有边信息，格式为边的两个顶点和权重，使用空格分隔。 eg:a b weight,如果全部信息输入完毕请输入end")
    while True:
        tempSide = input(">:")
        if tempSide.strip().lower() == "end":
            print("输入结束")
            break
        tempNodeList = tempSide.strip().split(" ")
        if len(tempNodeList) == 3:
            if tempNodeList[0] in graphNodeList and tempNodeList[1] in graphNodeList:
                createDigraphAdjMatrixWeight(tempNodeList[0], tempNodeList[1], int(tempNodeList[2]))
            else:
                print("边信息输入有误，请重新输入")
            continue
        else:
            print("输入有误请重新输入")
            continue

#初始化邻接矩阵;注意多维数组初始化格式以及数据的浅拷贝坑
def initGraphAdjMatrixWeight(nodeNum):
    for row in range(nodeNum):
        tempList = []
        for column in range(nodeNum):
            tempList.append(MAX)
        graphAdjMatrix.append(tempList)

#根据输入顶点信息完成邻接表
def createUndigraphAdjMatrix(node0, node1):
    tempIndex1 = graphNodeList.index(node0)
    tempIndex2 = graphNodeList.index(node1)
    graphAdjMatrix[tempIndex1][tempIndex2] = 1
    graphAdjMatrix[tempIndex2][tempIndex1] = 1

def createDigraphAdjMatrix(node0, node1):
    tempIndex1 = graphNodeList.index(node0)
    tempIndex2 = graphNodeList.index(node1)
    graphAdjMatrix[tempIndex1][tempIndex2] = 1

def createDigraphAdjMatrixWeight(node0, node1, weight):
    tempIndex1 = graphNodeList.index(node0)
    tempIndex2 = graphNodeList.index(node1)
    graphAdjMatrix[tempIndex1][tempIndex2] = weight

#pRINT输出空格和换行的写法
def printAdjMatrix(nodeNum):
    for row in range(nodeNum):
        for column in range(nodeNum):
            print(graphAdjMatrix[row][column], end=" ")
        print("")

def maindigAdjMatWeight():
    acquireNode()
    initGraphAdjMatrixWeight(len(graphNodeList))
    acquireSideDigWeight()

def dijkstra(startnode):
    ##初始化
    for node in graphNodeList:
        # 初始化集合S,在集合S中的点在searchNodeInfo对应位置为True，默认初始化为False
        if node == startnode:
            searchNodeInfo.append(True)
        else:
            searchNodeInfo.append(False)
    for index, value in enumerate(graphAdjMatrix[graphNodeList.index(startnode)]):
        # 初始化前驱列表p;将startnode的邻接点前驱初始化为startnode，否则初始化为-1;初始化最短路径长度dist
        dist.append(value)
        if value < MAX:
            p.append(startnode)
        else:
            p.append(-1)
    ##将查找最小邻接点和使用最小邻接点更新dist p列表循环n-1次即可将所有数据更新完毕,起点已经是确定
    for loop in range(len(graphNodeList)-1):
        ##找dist中searchpath为False的最小值.
        tempdist = []
        for index, value in enumerate(searchNodeInfo):
            if value is False:
                tempdist.append(dist[index])
        #根据找到的最小值更新searchPath,判断节点是否查询完成;查询完成程序返回
        tempindex = dist.index(sorted(tempdist)[0])
        searchNodeInfo[tempindex] = True
        if False not in searchNodeInfo:
            printdijkstra(startnode)
            return 0
        #否则使用新加到search的节点更新其邻接点的dist值和p前驱
        for index, value in enumerate(graphAdjMatrix[tempindex]):
            if searchNodeInfo[index] is False and dist[index] > dist[tempindex] + value:
                dist[index] = dist[tempindex] + value
                p[index] = graphNodeList[tempindex]
    printdijkstra(startnode)
#输出原始节点到其它节点的最短路径长度和路径上的顶点
def printdijkstra(startnode):
    for i in range(len(graphNodeList)):
        if i == graphNodeList.index(startnode):
            print("这是起点自己%s" %startnode)
        else:
            print("起始点到顶点%s的距离是%d" %(graphNodeList[i], dist[i]),end="。")
            print("访问路径为:", end=" ")
            temppath = []
            temp_pi = i
            #找到顶点的所有前驱拼接起来即为最优路径
            while True:
                if p[temp_pi] != -1:
                    temppath.append(p[temp_pi])
                    temp_pi = graphNodeList.index(p[temp_pi])

                else:
                    break
            temppath.reverse()
            for path in temppath:
                print("%s->" % path, end="")
            print(graphNodeList[i])

if __name__ == "__main__":
    maindigAdjMatWeight()
    dijkstra(graphNodeList[0])

View Code