Self-defined Dijkstra's algorithm in Python

Question

I can successfully ran the codes that are not in a function format. However, once I packaged everything into a function. I will receive an error. The data is as following:

# A
graph_a = {}
graph_a['s'] = {}
graph_a['a'] = {}
graph_a['b'] = {}
graph_a['c'] = {}
graph_a['d'] = {}
graph_a['f'] = {}
graph_a['s']['a'] = 2
graph_a['s']['b'] = 5
graph_a['a']['b'] = 8
graph_a['a']['d'] = 7
graph_a['b']['d'] = 2
graph_a['b']['c'] = 4
graph_a['c']['d'] = 6
graph_a['c']['f'] = 3
graph_a['d']['f'] = 1

cost_a = {}
cost_a['a'] = 2
cost_a['b'] = 5
cost_a['f'] = float('inf')
cost_a['c'] = float('inf')
cost_a['d'] = float('inf')

parent_a = {}
parent_a['a'] = 's'
parent_a['b'] = 's'
parent_a['c'] = None
parent_a['d'] = None
parent_a['f'] = None

I also defined the lowest cost node function to find the lowest cost node in the cost in each iteration.

searched = []

def lowestcostnode(x):
    lowestnode = None
    lowestcost = float('inf')
    for node in x:
        if x[node] < lowestcost and node not in searched:
            lowestcost = x[node]
            lowestnode = node
    return lowestnode

I can get the results successfully via:

searched = []
node = lowestcostnode(cost_a)
while node is not None:
    currentcost = cost_a[node]
    neighbors = graph_a[node]
    for n in neighbors:
        if cost_a[n] > currentcost + neighbors[n]:
            cost_a[n] = currentcost + neighbors[n]
            parent_a[n] = node
    searched.append(node)
    node = lowestcostnode(cost_a)

The result is as:

cost_a
{'a': 2, 'b': 5, 'f': 8, 'c': 9, 'd': 7}

But once I tried to packed the codes into a function, I got error message:

The function will generate error message as following if I create the searched list within the function:

def dijkstra(graph, parent, cost):
    searched = []
    node = lowestcostnode(cost)
    while node is not None:
        currentcost = cost[node]
        neighbors = graph[node]
        for n in neighbors:
            if cost[n] > currentcost + neighbors[n]:
                cost[n] = currentcost + neighbors[n]
                parent[n] = node
        searched.append(node)
        node = lowestcostnode(cost)
    print('parent as:', parent)
    print('cost as:', cost)
    return parent, cost

The error will be:

dijkstra(graph_a, cost_a, parent_a)
---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-57-00f1df255994> in <module>
----> 1 dijkstra(graph, parent, cost)

<ipython-input-56-517377fe9acb> in dijkstra(graph, parent, cost)
     12 def dijkstra(graph, parent, cost):
     13     searched = []
---> 14     node = lowestcostnode(cost)
     15     while node is not None:
     16         currentcost = cost[node]

<ipython-input-56-517377fe9acb> in lowestcostnode(x)
      5     lowestcost = float('inf')
      6     for node in x:
----> 7         if x[node] < lowestcost and node not in searched:
      8             lowestcost = x[node]
      9             lowestnode = node

NameError: name 'searched' is not defined

However, I already defined the searched one line before calling the lowestcostnode function.

Thank you in advance for your help.

george · Accepted Answer · 2020-11-17 03:38:50Z

1

You are calling: dijkstra(graph_a, cost_a, parent_a) but based on your function definition I would expect: dijkstra(graph_a, parent_a, cost_a)

Does this fix your problem?

answered Nov 17, 2020 at 3:38

george

1,8491 gold badge18 silver badges16 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Qiang Super Over a year ago

Thank you for pointing this out. It partially fixed the problem, but once I inserted the searched = [] within the function, I will receive error message. I updated the question then.

george Over a year ago

pass search as an argument. If you put search in the function then it is a local variable so other functions don't know about its existence. def lowestcostnode(x, search):

Qiang Super Over a year ago

Thank you. Even I claimed this variable in the function, and then called another function in this function. In this case, the claimed variable is still the local variable to this function and can't be recognized in another function called within this function?

Collectives™ on Stack Overflow

Self-defined Dijkstra's algorithm in Python

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related