Return to Question

Code below is superior to my version

class Graph:

    def __init__(self):
        self.nodes = {}

    def add_node(self, key, neighbours):
        self.nodes[key] = neighbours

    def shortest_path(self, start, finish):
        distance = {}  # stores distance to start node of a vertex
        visited = {}  # stores previously visited node
        queue = {}  # PQ that gives the shortest value from start to a vertex

        for node in self.nodes:
            if node == start:
                distance[node] = 0  # as distance from start node is 0
                queue[node] = 0  # value of root node to root node is 0

            else:
                distance[node] = 1000  # set unvisited nodes arc length to large value
                queue[node] = 1000

        while len(queue) != 0:
            if start == finish:
                print("start node and end node are same so distance is 0")
                break

            # works out arc with lowest weight
            lowest = 1000
            lowest_key = None
            for key in queue:
                if queue[key] < lowest:
                    lowest = queue[key]
                    lowest_key = key
            del queue[lowest_key]

            if distance[lowest_key] == 1000:
                print("No traversable paths left")
                break

            elif lowest_key == finish:
                shortest_path = []
            while True:
                temp_val = visited[lowest_key]
                shortest_path.append(temp_val)
                lowest_key = visited[lowest_key]
                if lowest_key == start:
                     break
            print(shortest_path)

            else:
                for neighbour in self.nodes[lowest_key].keys():  # checks neighbours of node released from pq
                    # adds value of neighbour arc to distance of previous node
                    alt_path = distance[lowest_key] + self.nodes[lowest_key][neighbour]
                    # if new path is shorter than distance of node in pq , then pq should be updated
                    if alt_path < distance[neighbour]:
                        distance[neighbour] = alt_path  # changes distance
                        visited[neighbour] = lowest_key  # adds this node to visited dict
                        # now changes are made to pq
                        for node in queue.keys():
                            if node == neighbour:
                                queue[node] = alt_path


g = Graph()
g.add_node('A', {'B': 5, 'C': 1})
g.add_node('B', {'D': 2, 'A': 5})
g.add_node('C', {'D': 9, 'A': 1})
g.add_node('D',{'B': 2, 'C': 9})
g.shortest_path("A",'D')

class Graph:

    def __init__(self):
        self.nodes = {}

    def add_node(self, key, neighbours):
        self.nodes[key] = neighbours

    def shortest_path(self, start, finish):
        distance = {}  # stores distance to start node of a vertex
        visited = {}  # stores previously visited node
        queue = {}  # PQ that gives the shortest value from start to a vertex

        for node in self.nodes:
            if node == start:
                distance[node] = 0  # as distance from start node is 0
                queue[node] = 0  # value of root node to root node is 0

            else:
                distance[node] = 1000  # set unvisited nodes arc length to large value
                queue[node] = 1000

        while len(queue) != 0:
            if start == finish:
                print("start node and end node are same so distance is 0")
                break

            # works out arc with lowest weight
            lowest = 1000
            lowest_key = None
            for key in queue:
                if queue[key] < lowest:
                    lowest = queue[key]
                    lowest_key = key
            del queue[lowest_key]

            if distance[lowest_key] == 1000:
                print("No traversable paths left")
                break

            elif lowest_key == finish:
                shortest_path = []
            while True:
                temp_val = visited[lowest_key]
                shortest_path.append(temp_val)
                lowest_key = visited[lowest_key]
                if lowest_key == start:
                     break
            print(shortest_path)

            else:
                for neighbour in self.nodes[lowest_key].keys():  # checks neighbours of node released from pq
                    # adds value of neighbour arc to distance of previous node
                    alt_path = distance[lowest_key] + self.nodes[lowest_key][neighbour]
                    # if new path is shorter than distance of node in pq , then pq should be updated
                    if alt_path < distance[neighbour]:
                        distance[neighbour] = alt_path  # changes distance
                        visited[neighbour] = lowest_key  # adds this node to visited dict
                        # now changes are made to pq
                        for node in queue.keys():
                            if node == neighbour:
                                queue[node] = alt_path


g = Graph()
g.add_node('A', {'B': 5, 'C': 1})
g.add_node('B', {'D': 2, 'A': 5})
g.add_node('C', {'D': 9, 'A': 1})
g.add_node('D',{'B': 2, 'C': 9})
g.shortest_path("A",'D')

Code below is superior to my version

1. Dictionary used for priority queue.
2. Priority queue should be its own class, but I dont know how to call a method from one class to another, I did research this and came across staticmethod but was unsure of its implementation.
3. The code to print the shortest path does not work properly as intended , it runs but only because I add the root node onto the shortest path at the end, I am aware of this but my solution to this used a while True loop, and was much longer than this way.
4. This was all done on one single file.

class Graph:

    def __init__(self):
        self.nodes = {}

    def add_node(self, key, neighbours):
        self.nodes[key] = neighbours

    def shortest_path(self, start, finish):
        distance = {}  # stores distance to start node of a vertex
        visited = {}  # stores previously visited node
        queue = {}  # PQ that gives the shortest value from start to a vertex

        for node in self.nodes:
            if node == start:
                distance[node] = 0  # as distance from start node is 0
                queue[node] = 0  # value of root node to root node is 0

            else:
                distance[node] = 1000  # set unvisited nodes arc length to large value
                queue[node] = 1000

        while len(queue) != 0:
            if start == finish:
                print("start node and end node are same so distance is 0")
                break

            # works out arc with lowest weight
            lowest = 1000
            lowest_key = None
            for key in queue:
                if queue[key] < lowest:
                    lowest = queue[key]
                    lowest_key = key
            del queue[lowest_key]

            if distance[lowest_key] == 1000:
                print("No traversable paths left")
                break

            elif lowest_key == finish:
                shortest_path = []
                #  Not working as intended , needs to check for and include root node in shortest path
                while visited[lowest_key] != start:
                    temp_val = visited[lowest_key]
                    shortest_path.append(temp_val)
                    lowest_key = visited[lowest_key]
                shortest_path.append(start)
                print(shortest_path)

            else:
                for neighbour in self.nodes[lowest_key].keys():  # checks neighbours of node released from pq
                    # adds value of neighbour arc to distance of previous node
                    alt_path = distance[lowest_key] + self.nodes[lowest_key][neighbour]
                    # if new path is shorter than distance of node in pq , then pq should be updated
                    if alt_path < distance[neighbour]:
                        distance[neighbour] = alt_path  # changes distance
                        visited[neighbour] = lowest_key  # adds this node to visited dict
                        # now changes are made to pq
                        for node in queue.keys():
                            if node == neighbour:
                                queue[node] = alt_path


g = Graph()
g.add_node('A', {'B': 5, 'C': 1})
g.add_node('B', {'D': 2, 'A': 5})
g.add_node('C', {'D': 9, 'A': 1})
g.add_node('D',{'B': 2, 'C': 9})
g.shortest_path("A",'D')

1. Dictionary used for priority queue.
2. Priority queue should be its own class, but I dont know how to call a method from one class to another, I did research this and came across staticmethod but was unsure of its implementation.
3. This was all done on one single file.

class Graph:

    def __init__(self):
        self.nodes = {}

    def add_node(self, key, neighbours):
        self.nodes[key] = neighbours

    def shortest_path(self, start, finish):
        distance = {}  # stores distance to start node of a vertex
        visited = {}  # stores previously visited node
        queue = {}  # PQ that gives the shortest value from start to a vertex

        for node in self.nodes:
            if node == start:
                distance[node] = 0  # as distance from start node is 0
                queue[node] = 0  # value of root node to root node is 0

            else:
                distance[node] = 1000  # set unvisited nodes arc length to large value
                queue[node] = 1000

        while len(queue) != 0:
            if start == finish:
                print("start node and end node are same so distance is 0")
                break

            # works out arc with lowest weight
            lowest = 1000
            lowest_key = None
            for key in queue:
                if queue[key] < lowest:
                    lowest = queue[key]
                    lowest_key = key
            del queue[lowest_key]

            if distance[lowest_key] == 1000:
                print("No traversable paths left")
                break

            elif lowest_key == finish:
                shortest_path = []
            while True:
                temp_val = visited[lowest_key]
                shortest_path.append(temp_val)
                lowest_key = visited[lowest_key]
                if lowest_key == start:
                     break
            print(shortest_path)

            else:
                for neighbour in self.nodes[lowest_key].keys():  # checks neighbours of node released from pq
                    # adds value of neighbour arc to distance of previous node
                    alt_path = distance[lowest_key] + self.nodes[lowest_key][neighbour]
                    # if new path is shorter than distance of node in pq , then pq should be updated
                    if alt_path < distance[neighbour]:
                        distance[neighbour] = alt_path  # changes distance
                        visited[neighbour] = lowest_key  # adds this node to visited dict
                        # now changes are made to pq
                        for node in queue.keys():
                            if node == neighbour:
                                queue[node] = alt_path


g = Graph()
g.add_node('A', {'B': 5, 'C': 1})
g.add_node('B', {'D': 2, 'A': 5})
g.add_node('C', {'D': 9, 'A': 1})
g.add_node('D',{'B': 2, 'C': 9})
g.shortest_path("A",'D')