graph = {}
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"] = {"fin": 1} # graph["a"]["fin"] = 1
graph["b"] = {"a": 3, "fin": 5} # graph["b"]["a"] = 3 graph["b"]["fin"] = 5
graph["fin"] = {}
# Hash table that stores the price of a node
In infinity = float("inf") # Python, the infinite representation method uses float('inf').
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity
# Hashtables for Parents
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None
processed = [] # Each node needs to be processed only once, so a list of nodes that have already been processed is needed.
# Function to find the cheapest node
def find_lowest_cost_node(costs):
lowest_cost = float("inf")
lowest_cost_node = None
For node in costs: # In the cost table, rotate nodes one by one
cost = costs[node] # cost = {'a' : 6, 'b' : 2, fin : infinity}
If cost < lowest_cost and node not in process: # The cost of the node being verified is lower than the minimum cost and the node is not processed
lowest_cost = cost # Renew lowest cost
lowest_cost_node = node # Update the lowest cost node
return lowest_cost_node
node = find_lowest_cost_node(costs) # Find the cheapest node that has not yet been processed. # # b
# End of repeat statement after processing all nodes processed
while node is not None:
cost = costs[node] #cost = {'a' : 6, 'b' : 2, 'fin' : infinity} #initial cost = costs[b] = 2
neighbors = graph[node] # neighbors = {'a' : {'fin' : 1}, 'b' : {'a': 3, 'fin': 5}, 'fin' : {} }
For n in neighbors.keys(): # Repeat for all neighbors [start][a] = 6 [start][b] = 2 [a][fin] = 1 [b][a] = 3 [b][fin] = 5
new_cost = cost + neighbors[n]
If costs[n] > new_cost: # If passing through a new node is cheaper,
costs[n] = new_cost # Update the price of the node to the price of the new node
parents[n] = node # Set parent to this node new
Processed.append(node) # Record the fact that the node was processed
node = find_lowest_cost_node(costs) # Find and repeat the node you want to handle next
print('Parent Table (Route Move):')
print(parents)
print('shortest distance node cost :')
print(costs)
# Output result
# Parent table (path move):
# # {'a': 'b', 'b': 'start', 'fin': 'a'}
# The shortest distance node cost is:
# # {'a': 5, 'b': 2, 'fin': 6}
I understood the meaning of the Dijkstra algorithm. But it's hard to analyze the code that this algorithm is implemented;; The actual output and the analysis were different crying I don't know why start is included in the parent table ㅠ<
So is node = find_lowest_cost_node(costs) = 2 at first?
If you look at the order in which the for statement is executed n = a -> new_cost = 2 + 3 = 5 -> costsa > new_cost -> costs[a] = 5 -> parents[a] = b n = fin -> new_cost = 2 + 5 = 7 -> costsfin > new_cost -> costs[fin] = 7 -> parents[fin] = b processed = [b] Does it work?
python dijkstra algorithm graph table
parent records the node before the node is visited when it is visited by the best path. Since you moved from start to b, the parent of b becomes start. When you output a path, you can start at the end, stack it on the stack, and then output it.
List item
At first, it says b.
Visit b -> a -> fin and fin has never had a cost of 7.
© 2024 OneMinuteCode. All rights reserved.