Basic Dijkstras Implementation - Printable Version +- Python Forum (https://python-forum.io) +-- Forum: Python Coding (https://python-forum.io/forum-7.html) +--- Forum: Homework (https://python-forum.io/forum-9.html) +--- Thread: Basic Dijkstras Implementation (/thread-15557.html) |
Basic Dijkstras Implementation - grandpapa10 - Jan-22-2019 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... RE: Basic Dijkstras Implementation - Larz60+ - Jan-22-2019 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() RE: Basic Dijkstras Implementation - grandpapa10 - Jan-22-2019 Jesus, many thanks ! One quick dumb question… How should I run the code now ? Should I initialize as shortpath(graph, 'C', 'I')? RE: Basic Dijkstras Implementation - Larz60+ - Jan-22-2019 this can be run from command line: python programname.pyor from within Jupiter you need to remove line 71 and indentation from line 72 RE: Basic Dijkstras Implementation - grandpapa10 - Jan-22-2019 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.pyin a different cell after removing line 71 and the indentation from line 72... Got Invalid Syntax error :((( RE: Basic Dijkstras Implementation - grandpapa10 - Jan-22-2019 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 ? RE: Basic Dijkstras Implementation - Larz60+ - Jan-22-2019 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. RE: Basic Dijkstras Implementation - grandpapa10 - Jan-23-2019 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 ! |