Python Forum
Basic Dijkstras Implementation
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Basic Dijkstras Implementation
#2
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()
Reply


Messages In This Thread
Basic Dijkstras Implementation - by grandpapa10 - Jan-22-2019, 12:09 AM
RE: Basic Dijkstras Implementation - by Larz60+ - Jan-22-2019, 08:40 AM
RE: Basic Dijkstras Implementation - by grandpapa10 - Jan-22-2019, 10:28 AM
RE: Basic Dijkstras Implementation - by Larz60+ - Jan-22-2019, 10:51 AM
RE: Basic Dijkstras Implementation - by grandpapa10 - Jan-22-2019, 10:59 AM
RE: Basic Dijkstras Implementation - by grandpapa10 - Jan-22-2019, 01:42 PM
RE: Basic Dijkstras Implementation - by Larz60+ - Jan-22-2019, 03:57 PM
RE: Basic Dijkstras Implementation - by grandpapa10 - Jan-23-2019, 11:50 AM

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020