I would like to ask you a question about analyzing the example code that implements the Dijkstra algorithm in Python. (Help me!!!))

Asked 2 years ago, Updated 2 years ago, 140 views

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

2022-09-21 21:03

1 Answers

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.


2022-09-21 21:03

If you have any answers or tips


© 2024 OneMinuteCode. All rights reserved.