Shulou(Shulou.com)06/02 Report--

How to implement a Dijkstra algorithm in python? aiming at this problem, this article introduces the corresponding analysis and solution in detail, hoping to help more partners who want to solve this problem to find a more simple and feasible method.

"

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; dis 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 03 - 测试

Find the shortest path from A to each node in the above figure:

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))

The print result is as follows:

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

This is the answer to the question about how to implement a Dijkstra algorithm in python. I hope the above content can be of some help to everyone. If you still have a lot of doubts to be solved, you can follow the industry information channel to learn more about it.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.