Basic Dijkstras Implementation

[grandpapa10]

Hey there,


I m trying to run a code for a basic Dijkstra s Algo Implementation...
Unfortunately it s to no avail…
Whenever I try to run my code on the jupyter notebook, I experience some trouble with the kernel.

It simply won't run and cell gets stuck in [*].

I d appreciate if somebody could take a quick look at my code:

graph = {
       'A': {'B': 10, 'D': 4, 'F': 10},
       'B': {'E': 5, 'J': 10, 'I': 17},
       'C': {'A': 4, 'D': 10, 'E': 16},
       'D': {'F': 12, 'G': 21},
       'E': {'G': 4},
       'F': {'H': 3},
       'G': {'J': 3},
       'H': {'G': 3, 'J':5},
       'I': {},
       'J': {'I': 8},
    }
    
Class Graph:
def shortpath(graph, start, end):
    D = {} # final distances dict
    P = {} # Predecessor dict
    #Fill the dicts with default values
    for node in graph.keys():
        D[node] = - 1 # Vertices are unreachable
        P[node] = "" # Vertices have no predecessors
        
    D[start] = 0 # The start vertex needs no move
    
    unseen_nodes = graph.keys() # All nodes are unseen
    
    while len(unseen_nodes) > 0:
        # Select the node with the lowest value in D (final distance)
        shortest = None
        node = ''
        for temp_node in unseen_nodes:
            if shortest == None:
                shortest = D[temp_node]
                node = temp_node
            elif D[temp_node] < shortest:
                shortest = D[temp_node]
                node = temp_node
#remove the selected node from unseen_nodes

    unseen_nodes.remove(node)

#for each child (connected vertex) of the current node
    for child_node, child_value in graph[node].items():
        if D[child_node] < D[node] + child_value:
            D[child_node] = D[node] + child_value
            #To go to child_node, you have to go through node
            P[child_node] = node
#Set a clean path
            path = []
# we begin from the end 
            node = end
#while we are not arrived at the beginning

    while not (node == start):
        if path.count(node) == 0:
            path.insert(0, node) #Insert the predecessor of the current node
            node = P[node] # The current node becomes its predecessor
        else:
            break
            path.insert(0, start)#Finally, insert the start vertex
        return path

shortpath(graph, 'C', 'I')

sorry, I ve got a little problem with the indentation…

I just tried to run it again after updating the 'Class Graph' statement…
I also tried running the "def shortpath" in another cell, but NameError pops up saying that the "shortpath" is not defined...

[Larz60+]

there are a lot of issues here.
pointing out a few:
line 14: Class Graph: --> should be class Graph: # no capital letter on 'class'
line 15: indentation (indent 4 spaces)
There are many more indentation errors (I'm not sure what your intent was, for example line 40, can't tell what it's scope should be)

Edited 5:05 A.M. EST
here's a running version.
Note: moved graph into class initialization
cast line 27 (dictionary keys) to list so that line 44 remove will work on newer versions of python
(dictionaries are now ordered by default in python 3.7, do dict.keys is dict_key object, not list and remove will not work)
corrected indentation issues
changed 'Class' to 'class'
changed class variables to 'self' where needed
added 'self' to method attributes
** Note ** I use f-strings in commented out print statements which requires python 3.6 or newer python.

class Graph:
    def __init__(self):
        self.graph = {
           'A': {'B': 10, 'D': 4, 'F': 10},
           'B': {'E': 5, 'J': 10, 'I': 17},
           'C': {'A': 4, 'D': 10, 'E': 16},
           'D': {'F': 12, 'G': 21},
           'E': {'G': 4},
           'F': {'H': 3},
           'G': {'J': 3},
           'H': {'G': 3, 'J':5},
           'I': {},
           'J': {'I': 8}
        }

    def shortpath(self, start, end):
        D = {} # final distances dict
        P = {} # Predecessor dict
        #Fill the dicts with default values
        for node in self.graph.keys():
            D[node] = - 1 # Vertices are unreachable
            P[node] = "" # Vertices have no predecessors
            
        D[start] = 0 # The start vertex needs no move
        
        # print(f'D: {D}\nP: {P}')
        unseen_nodes = list(self.graph.keys()) # All nodes are unseen
        
        while len(unseen_nodes) > 0:
            # print(f'unseen_nodes: {unseen_nodes}')
            # Select the node with the lowest value in D (final distance)
            shortest = None
            node = ''
            for temp_node in unseen_nodes:
                if shortest == None:
                    shortest = D[temp_node]
                    node = temp_node
                elif D[temp_node] < shortest:
                    shortest = D[temp_node]
                    node = temp_node
                    #remove the selected node from unseen_nodes
    
                if node in unseen_nodes:
                    unseen_nodes.remove(node)
 
        #for each child (connected vertex) of the current node
        for child_node, child_value in self.graph[node].items():
            if D[child_node] < D[node] + child_value:
                D[child_node] = D[node] + child_value
                #To go to child_node, you have to go through node
                P[child_node] = node
                #Set a clean path
                path = []
                # we begin from the end 
                node = end

        #while we are not arrived at the beginning
        while not (node == start):
            if path.count(node) == 0:
                path.insert(0, node) #Insert the predecessor of the current node
                node = P[node] # The current node becomes its predecessor
            else:
                break
                path.insert(0, start)#Finally, insert the start vertex
            return path

def main():
    gg = Graph()
    gg.shortpath('C', 'I')

if __name__ == '__main__':
    main()

[grandpapa10]

Jesus, many thanks !

One quick dumb question… How should I run the code now ?

Should I initialize as

shortpath(graph, 'C', 'I')

?

[Larz60+]

this can be run from command line:

python programname.py

or from within Jupiter you need to remove line 71 and indentation from line 72

[grandpapa10]

ok... remove line 71 and indentation from line 72..
after that, in a next cell

python programname.py

?
and then

shortpath(graph, 'C', 'I')

?

I ran

python programname.py

in a different cell after removing line 71 and the indentation from line 72... Got Invalid Syntax error :(((

[grandpapa10]

Sorry, what I really meant was, How can I get the results ?
That is, what command should I give in the Jupyter notebook in order to retrieve the shortest path in the graph ?

[Larz60+]

I didn't actually look much at the logic, as this is a homework assignment left that up to you.
just got what you had to run. I had to guess on what belonged where.
Taking a quick look at login, it appears that what will get returned by shortpath is path from line 65,
nothing else.
You need to sit down and examine the logic and see what is happening.
I'd suggest installing an IDE with a debugger and single stepping to see the results of each step.
Also, while taking a quick look, see much room for improving logic and shortening code considerably.

Finally, your post 5 is wrong, read my post 4 again, carefully.

Hint remember, you can print at any time even just to see what some small piece of code is doing, and remove after satisfied.

[grandpapa10]

Hey Larz60,

I did you what you told me... had to start my code all over again.. But had some success with it !

Thanks a lot for your help !