Python Dijkstra Algorithm Memory Error?

Question

I have copied and pasted this answer for Dijkstra Algorithm to my project. It seemed ok after several simple tests.

In my specific implementation, I need the algorithm to return a list of nodes. So I have to modify the original code so that it always returns a list. More specifically, I removed all the return "string" lines there. The modified code by me is as follows:

## using Dijkstra Algorithm ##
def choosePath(s, t):
    net = {'0':{'1':138, '9':150},
       '1':{'0':138, '2':178, '8':194},
       '2':{'1':178, '3':47.5},
       '3':{'2':47.5, '4':70},
       '4':{'3':70, '5':70},
       '5':{'4':70, '6':36},
       '6':{'5':36, '7':50},
       '7':{'6':50, '8':81},
       '8':{'7':81, '9':138, '1':194},
       '9':{'8':138, '0':150}}
    # sanity check
    if s == t:
        return []
    # create a labels dictionary
    labels={}
    # record whether a label was updated
    order={}
    # populate an initial labels dictionary
    for i in net.keys():
        if i == s: labels[i] = 0 # shortest distance form s to s is 0
        else: labels[i] = float("inf") # initial labels are infinity
    from copy import copy
    drop1 = copy(labels) # used for looping
    ## begin algorithm
    while len(drop1) > 0:
        # find the key with the lowest label
        minNode = min(drop1, key = drop1.get) #minNode is the node with the smallest label
        # update labels for nodes that are connected to minNode
        for i in net[minNode]:
            if labels[i] > (labels[minNode] + net[minNode][i]):
                labels[i] = labels[minNode] + net[minNode][i]
                drop1[i] = labels[minNode] + net[minNode][i]
                order[i] = minNode
        del drop1[minNode] # once a node has been visited, it's excluded from drop1
    ## end algorithm
    # print shortest path
    temp = copy(t)
    rpath = []
    path = []
    while 1:
        rpath.append(temp)
        if order.has_key(temp):
            temp = order[temp]
        if temp == s:
            rpath.append(temp)
            break
    for j in range(len(rpath)-1,-1,-1):
        path.append(rpath[j])
    return [junctions[int(elem)] for elem in path]

Then when I run it, I end up with the following error:

>>> Traceback (most recent call last):
  File "C:\Users\...\simulation.py", line 162, in choosePath
    rpath.append(temp)
MemoryError

Obviously, it is because I have removed the return "string" lines. However, I failed to find out which deletion makes it die. Why is it so?

How may I make it work again AND always returns a list instead of a string as I wish?

It sure sounds like it's adding nodes to rpath until you run out of memory. I'm not sure why that's happening, but perhaps you could add code to catch the exception if it happens and print out rpath and the order dictionary? That should give you a good idea of what's going wrong. — Blckknght
– Blckknght, Commented Oct 4, 2013 at 9:49

Trevor Merrifield · Accepted Answer · 2013-10-05 07:29:34Z

I suspect your problem is that you're passing the wrong arguments to the function. You want to call choosePath('0', '9'). Strings. Not integers.

What's comical is that if ANY of the parts of the program you removed were still there, it would have caught this and stopped the program. With this part, it catches if your input is wrong.

if net.has_key(s)==False:
    return "There is no start node called " + str(s) + "."
if net.has_key(t)==False:
    return "There is no terminal node called " + str(t) + "."

With this part, it catches if it never reaches a solution.

else: return "There is no path from " + str(s) + " to " + str(t) + "."

The sanity checks are not strictly necessary, since as you mentioned a path is assured in your net. Still the checks are nice because if you ever do choose to change things around you'll know the computer will call you out on obvious mistakes. One option is to replace them with exceptions, since none of these messages should really come up unless something has gone horribly wrong. That's what I opted for in the following code.

class NoPathException(Exception):
    pass

def choosePath(s, t):
    net = {'0':{'1':138, '9':150},
       '1':{'0':138, '2':178, '8':194},
       '2':{'1':178, '3':47.5},
       '3':{'2':47.5, '4':70},
       '4':{'3':70, '5':70},
       '5':{'4':70, '6':36},
       '6':{'5':36, '7':50},
       '7':{'6':50, '8':81},
       '8':{'7':81, '9':138, '1':194},
       '9':{'8':138, '0':150}}
    # sanity check
    if s == t:
        return []
    if not net.has_key(s):
        raise ValueError("start node argument not in net")
    if not net.has_key(t):
        raise ValueError("end node argument not in net")
    # create a labels dictionary
    labels={}
    # record whether a label was updated
    order={}
    # populate an initial labels dictionary
    for i in net.keys():
        if i == s: labels[i] = 0 # shortest distance form s to s is 0
        else: labels[i] = float("inf") # initial labels are infinity
    from copy import copy
    drop1 = copy(labels) # used for looping
    ## begin algorithm
    while len(drop1) > 0:
        # find the key with the lowest label
        minNode = min(drop1, key = drop1.get) #minNode is the nod2 with the smallest label
        # update labels for nodes that are connected to minNode
        for i in net[minNode]:
            if labels[i] > (labels[minNode] + net[minNode][i]):
                labels[i] = labels[minNode] + net[minNode][i]
                drop1[i] = labels[minNode] + net[minNode][i]
                order[i] = minNode
        del drop1[minNode] # once a node has been visited, it's excluded from drop1
    ## end algorithm
    # print shortest path
    temp = copy(t)
    rpath = []
    path = []
    while 1:
        rpath.append(temp)
        if order.has_key(temp):
            temp = order[temp]
        else:
            raise NoPathException("no path to solution")
        if temp == s:
            rpath.append(temp)
            break
    for j in range(len(rpath)-1,-1,-1):
        path.append(rpath[j])

    return path

Testing

a = choosePath('3', '9')
print(a)
['3', '4', '5', '6', '7', '8', '9']

Is this the output you're looking for?

The 3 lines are exactly what I have removed. But indeed call choosePath('0', '9') with strings. Also, the reason why I think I can safely delete the else clause is that in my problem, a path is always assured to exist. Hence I am confused why this still shows up. But anyway you have given nice advice. I will try exception catches. Or I can just simply replace return with print right?
@perfectionm1ng I've updated the answer. Also replacing the returns with a print wouldn't be the best for one reason- it doesn't leave the function. Returns and exceptions both bail out.

Collectives™ on Stack Overflow

Python Dijkstra Algorithm Memory Error?

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related