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

• Volodymyr Safiyanyk: Hello! Thanks for the answer) I'll look for all problems you described ) 3.I'll look at how to do that) But can l print a node name in the loop instead of the new function? I will change the code looking at your answer)
• Akash Patel: print(str(the_node))
• Akash Patel: str(node) calls the str function on the node class. print(str(node)) outputs that str to the command line.