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.
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()