python中怎么實現(xiàn)一個Dijkstra算法

python中怎么實現(xiàn)一個Dijkstra算法，針對這個問題，這篇文章詳細介紹了相對應的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。

"""

Dijkstra algorithm

graphdict={"A":[("B",6),("C",3)], "B":[("C",2),("D",5)],"C":[("B",2),("D",3),("E",4)],\

         "D":[("B",5),("C",3),("E",2),("F",3)],"E":[("C",4),("D",2),("F",5)],"F":[("D",3),"(E",5)]})

assert: start node must be zero in-degree

"""

def Dijkstra(startNode, endNode, graphdict=None):

    S=[startNode]

    V=[]

    for node in graphdict.keys():

        if node !=startNode:

            V.append(node)

    #distance dict from startNode

    dist={}

    for node in V:

        dist[node]=float('Inf')

    while len(V)>0:

        center = S[-1] # get final node for S as the new center node

        minval = ("None",float("Inf"))

        for node,d in graphdict[center]:

            if node not in V:

                continue

            #following is the key logic.If S length is bigger than 1,need to get the final ele of S, which is the center point in current

            #iterator, and distance between start node and center node is startToCenterDist; d is distance between node

            # among out-degree for center point; dist[node] is previous distance to start node, possibly Inf or a updated value

            # so if startToCenterDist+d is less than dist[node], then it shows we find a shorter distance.

            if len(S)==1:

                dist[node] = d

            else:

                startToCenterDist = dist[center]

                if startToCenterDist + d < dist[node]:

                    dist[node] = startToCenterDist + d

            #this is the method to find a new center node and

            # it's the minimum distance among out-degree nodes for center node

            if d < minval[1]:

                minval = (node,d)

        V.remove(minval[0])

        S.append(minval[0]) # append node with min val

    return dist

測試

求出以上圖中，從A到各個節(jié)點的最短路徑：

shortestRoad = Dijkstra("A","F",graphdict={"A":[("B",6),("C",3)], "B":[("C",2),("D",5)],\

                            "C":[("B",2),("D",3),("E",4)],\

                            "D":[("B",5),("C",3),("E",2),("F",3)],\

                            "E":[("C",4),("D",2),("F",5)],"F":[("D",3),("E",5)]})

mystr = "shortest distance from A begins to "

for key,shortest in shortestRoad.items():

    print(mystr+ str(key) +" is: " + str(shortest) )

打印結(jié)果如下：

shortest distance from A begins to B is: 5

shortest distance from A begins to C is: 3

shortest distance from A begins to D is: 6

shortest distance from A begins to E is: 7

shortest distance from A begins to F is: 9

關(guān)于python中怎么實現(xiàn)一個Dijkstra算法問題的解答就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關(guān)注億速云行業(yè)資訊頻道了解更多相關(guān)知識。