# Dijkstra's algorithm in graph (Python)

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

if self.graphStructure.get(index) is None:
self.graphStructure[index] = node(index, [], [], False)

n0 = self.graphStructure.get(node0_name)

n1 = self.graphStructure.get(node1_name)

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

node0, node1, length = map(int, input().split())

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

# 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.

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

1. 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
• 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) Jan 8 at 7:52
• print(str(the_node)) Jan 9 at 17:35
• str(node) calls the str function on the node class. print(str(node)) outputs that str to the command line. Jan 9 at 19:07