4
\$\begingroup\$

Unrelated to code:

  1. This is my first project in Python using classes and algorithms.
  2. I have spent the last week self teaching myself about queues and stacks, so I am NOT trying to use any Python libraries for this as I would like to know how to implement my own priority queue

About the code:

  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.

What I would like from this:

  1. A way to get the input for graph without having it already 'created' when code is run. I had an idea to get user input for each node and its arc length to every other node, but this is inefficient for larger graphs.
  2. General advice/feedback/issues with my code/logic
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')
\$\endgroup\$
  • \$\begingroup\$ Could you post the working shortest path function? It does not matter if it is longer, we review working code \$\endgroup\$ – Caridorc Sep 28 '16 at 20:19
  • \$\begingroup\$ As it is the code works as I simply add the root node on the end , but I will add modified version as well. \$\endgroup\$ – Ikm Sep 28 '16 at 20:20
  • \$\begingroup\$ Should be on there now. \$\endgroup\$ – Ikm Sep 28 '16 at 20:25
  • \$\begingroup\$ The priority queue data structure is implemented in the python library in the "heapq" module. You can do Djikstra without it, and just brute force search for the shortest next candidate, but that will be significantly slower on a large graph. You say you want to code your own. That should be in a list/array which follows the heap invariant. (want more info on implementing heap?) \$\endgroup\$ – Kenny Ostrom Sep 28 '16 at 23:59
  • 2
    \$\begingroup\$ I have rolled back the last edit. Please see What to do when someone answers. \$\endgroup\$ – Peilonrayz Oct 18 '16 at 13:40
4
\$\begingroup\$

A bug

For the shortest path from A to D, your implementation shows [B, A], which is wrong.

Indentation error

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)

should be indented once to the right; otherwise your code does not compile.

Efficiency

Use the priority queue in order to speed up your implementation:

import heapq


class HeapEntry:
    def __init__(self, node, priority):
        self.node = node
        self.priority = priority

    def __lt__(self, other):
        return self.priority < other.priority


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

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

    def traceback_path(self, target, parents):
        path = []
        while target:
            path.append(target)
            target = parents[target]
        return list(reversed(path))

    def shortest_path(self, start, finish):
        OPEN = [HeapEntry(start, 0.0)]
        CLOSED = set()
        parents = {start: None}
        distance = {start: 0.0}

        while OPEN:
            current = heapq.heappop(OPEN).node

            if current is finish:
                return self.traceback_path(finish, parents)

            if current in CLOSED:
                continue

            CLOSED.add(current)

            for child in self.nodes[current].keys():
                if child in CLOSED:
                    continue
                tentative_cost = distance[current] + self.nodes[current][child]

                if child not in distance.keys() or distance[child] > tentative_cost:
                    distance[child] = tentative_cost
                    parents[child] = current
                    heap_entry = HeapEntry(child, tentative_cost)
                    heapq.heappush(OPEN, heap_entry)

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})
print(g.shortest_path("A", 'D'))

Note also that we do not need anymore

for node in self.nodes:
    if node == start:
        distance[node] = 0 
        queue[node] = 0 
    else:
        distance[node] = 1000  
        queue[node] = 1000

Think about what happens if the graph is large but the terminal nodes are close to each other: you waste a lot of CPU cycles.

Hope that helps.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.