Djikstra's algorithm implementation within python with classes

[Aspect11]

So here's my code:

class Vertex:
    def __init__(self, name):
        self.name = name
        self.connections = {}

    def addNeighbour(self, neighbour, cost):
        self.connections[neighbour] = cost


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

    def addVertex(self, newVertex):
        new = Vertex(newVertex)
        self.vertexs[newVertex] = new

    def addEdge(self, src, dest, cost):
        self.vertexs[src].addNeighbour(self.vertexs[dest], cost)

    def dfs(self, start, end, visited):
        visited[start] = True
        print(start, end=' ')
        if start == end:
            # End node found
            return True
        else:
            # Use depth first search
            for connection in graph.vertexs[start].connections:
                if visited[connection.name] == False:
                    if self.dfs(connection.name, end, visited) == True:
                        # Return true to stop extra nodes from being searched
                        return True

    def bfs(self, start, end, visited, queue):
        if len(queue) == 0:
            # Queue is empty
            queue.append(start)
        visited[start] = True
        currentNode = queue.pop(0)
        print(currentNode, end=' ')
        if start == end:
            # End node found
            return True
        else:
            # Do breadth first search
            for connection in graph.vertexs[currentNode].connections:
                if visited[connection.name] == False:
                    # Queue all its unvisited neighbours
                    queue.append(connection.name)
            for newNode in queue:
                self.bfs(newNode, end, visited, queue)

    def dijkstra(self, start, end, visited, distances):
      visited[start] = True
      for count, connection in enumerate(graph.vertexs[start].connections):
        # Set each neighbour's distance
        cost = list(graph.vertexs[start].connections.values())
        distances[count] = cost[count]
      smallestIndex = min(distances, key=distances.get)
      for connection in graph.vertexs[start].connections:
        if visited[smallestIndex] == False:
          self.dijkstra(connection.name, end, visited, distances)


def setup():
    graphList = {
        # Node number: [destination number, cost]
        0: [[1, 4], [2, 2], [3, 5]],
        1: [[1, 1], [3, 2]],
        2: [[0, 3]],
        3: [[2, 5]]
    }
    count = 0
    graph = Graph()

    for i in range(len(graphList)):
        graph.addVertex(i)

    for arr in graphList.values():
        for i in range(len(arr)):
            graph.addEdge(count, arr[i][0], arr[i][1])
        count += 1
    return graph, graphList


graph, graphList = setup()


def g():
    print("DFS travsersal path from node 0 to node 3:")
    graph.dfs(0, 3, [False, False, False, False])
    print()

    print("BFS traversal path from node 0 to node 3")
    graph.bfs(0, 3, [False, False, False, False], [])
    print()

    print("Shortest possible path from node 0 to 3:")
    print()


graph.dijkstra(2, 3, [False, False, False, False], {0: float('inf'), 1: float('inf'), 2: float('inf'), 3: float('inf')})

What's meant to happen is that after node 2 (the start), the distances dictionary should be:

{0: 3, 1: inf, 2: inf, 3: inf}

This happens successfully, but when it moves onto node 0, the dictionary is now set to:

{0: 4, 1: 2, 2: 5, 3: inf}

What it is meant to be (as it adds up the distances):

{0: 3, 1: 7, 2: inf, 3: 5}

I don't know whats wrong so if anyone can find it, that'll be much appreciated. Thanks!

[wanderingfool2]

A key to debugging

{0: 4, 1: 2, 2: 5, 3: inf}

The values are 4, 2, 5...which matches your node 0 inputs (and are exactly 3 off the value, which happens to be the weight from hopping from node 2 to 0).  This would tell me you aren't adding in the values.

 

I could be wrong (been a while since doing Dijkstra).  Isn't it supposed to build out the list by comparing the minimum's?  You have the shortest index, but outside of the loops where it is setting the distances.  I would think you would need it inside the loop, and checking whether the distance distance is at a minimum (before setting it)...also add the weight of the node to getting to there.

[Aspect11]

5 minutes ago, wanderingfool2 said:

A key to debugging

{0: 4, 1: 2, 2: 5, 3: inf}

The values are 4, 2, 5...which matches your node 0 inputs (and are exactly 3 off the value, which happens to be the weight from hopping from node 2 to 0).  This would tell me you aren't adding in the values.

Damm, that's what I forgot. Thanks XD

6 minutes ago, wanderingfool2 said:

I could be wrong (been a while since doing Dijkstra).  Isn't it supposed to build out the list by comparing the minimum's?  You have the shortest index, but outside of the loops where it is setting the distances.  I would think you would need it inside the loop, and checking whether the distance distance is at a minimum (before setting it)...also add the weight of the node to getting to there.

I don't think so, but maybe I'm wrong.

 

Thanks anyway!