Dijkstra's algorithm in graph (Python)

Question

I need some help with the graph and Dijkstra's algorithm in Python 3. I tested this code (look below) at one site and it says to me that the code took too long. Can anybody suggest how to solve that? I don't know how to speed up this code. I read many sites but I didn't find normal examples...

P.S. this is a new code version with deque and something like this, but it's still too slow.

from collections import deque


class node: 

    def __init__(self, name, neighbors, distance, visited):
        self.neighbors = neighbors
        self.distance = distance
        self.visited = visited
        self.name = name
    
    def addNeighbor(self, neighbor_name, dist): # adding new neighbor and length to him
    
        if neighbor_name not in self.neighbors:
            self.neighbors.append(neighbor_name)
            self.distance.append(dist)

class graph:

    def __init__(self):
        self.graphStructure = {} # vocabulary with information in format: node_name, [neighbors], [length to every neighbor], visited_status 
    
    
    def addNode(self, index): # adding new node to graph structure
    
        if self.graphStructure.get(index) is None:
            self.graphStructure[index] = node(index, [], [], False)


    def addConnection(self, node0_name, node1_name, length): # adding connection between 2 nodes
        n0 = self.graphStructure.get(node0_name)

        n0.addNeighbor(node1_name, length)

        n1 = self.graphStructure.get(node1_name)
        n1.addNeighbor(node0_name, length)
    
    def returnGraph(self): # printing graph nodes and connections

        print('')
        for i in range(len(self.graphStructure)):
            nodeInfo = self.graphStructure.get(i + 1)
            print('name =', nodeInfo.name, '  neighborns =', nodeInfo.neighbors, '           length to neighborns =', nodeInfo.distance)
        
    def bfs(self, index): # bfs method of searching (also used Dijkstra's algorithm)

        distanceToNodes = [float('inf')] * len(self.graphStructure)
        distanceToNodes[index - 1] = 0
        currentNode = self.graphStructure.get(index)
        queue = deque()
        
        for i in range(len(currentNode.neighbors)):
            n = currentNode.neighbors[i]
            distanceToNodes[n - 1] = currentNode.distance[i]
            queue.append(n)
        
        while len(queue) > 0: # creating queue and visition all nodes
            u = queue.popleft()
            node_u = self.graphStructure.get(u)
            node_u.visited = True

            for v in range(len(node_u.neighbors)):
                node_v = self.graphStructure.get(node_u.neighbors[v])
                distanceToNodes[node_u.neighbors[v] - 1] =  min(distanceToNodes[node_u.neighbors[v] - 1], distanceToNodes[u - 1] + node_u.distance[v]) # update minimal length to node
                if not node_v.visited:
                    queue.append(node_u.neighbors[v])
                    
        return distanceToNodes

def readInputToGraph(graph): # reading input data and write to graph datatbase
    node0, node1, length = map(int, input().split())

    graph.addNode(node0)
    graph.addNode(node1)
    graph.addConnection(node0, node1, length)


def main():
  newGraph = graph()
  countOfNodes, countOfPairs = map(int, input().split())

  if countOfPairs == 0:
      print('0')
      exit()

  for _ in range(countOfPairs): # reading input data for n(countOfPairs) rows
      readInputToGraph(newGraph)

  # newGraph.returnGraph() # printing information

  print(sum(newGraph.bfs(1))) # starting bfs from start position

  

main()

The input graph structure may look like this:

15 17
3 7 2
7 5 1
7 11 5
11 5 1
11 1 2
1 12 1
1 13 3
12 10 1
12 4 3
12 15 1
12 13 4
1 2 1
2 8 2
8 14 1
14 6 3
6 9 1
13 9 2

I'm only learning python so I think I may be doing something wrong.

Answer 1

1. Making an str(which makes a string from an object) for the node class which would simplify the graph return method
   the str converts an object to a string type

2. is this a dense graph or sparse graph? Sparse Graphs have a lot less edges between vertices Sparse Graphs can be efficently used as adjency lists Dense Graphs can be efficnetly represented with an adjency matrix (2d list of bool) Note: if you are familar with binary, you can use an int to set and get bits in Python (more space efficent than 2d list)

3. I would suggest a new class for what to do when the algorithm reaches a node (such as NodeVisit) This new class can a function called call(node) and run as object(the_node) This allows diffrent code to run on node such as print out or add distances along a path

4. Dijkstra's algorithm has a lower Big O with a min priority que Min priority ques are similar to real life lines with priority levels and tasks This can be made from a list where left_row is 2 * row and right_row is (2 * row) + 1

5. Make a seperate function or even class for Dijkstra's algorithm Dijkstra's algorithm can be done using parallel lists for vertex, distance, prev vertex Looking up the wikipedia article for Dijkstra's Algorithm shows its psudo code

   6. If you plan to use node anywhere else then make self.visited a parallel array and not inside the node class Another situation where int and binary can be used for space efficency