I'm trying to implement Dijkstra's algorithm to find the shortest distances of all vertices from the source vertex 1.
This is my implementation:
from ast import literal_eval
p = {}
with open(r'dijk.txt') as file:
for line in file:
line_content = line.split()
p[int(line_content[0])] = [literal_eval(edge) for edge in line_content[1:]]
source_vertex = next(iter(p.keys()))
print("Vertex 1's paths:", p[1])
print("1st value for vertex 1:", p[1][0])
print("1st neighbour of vertex 1:",p[1][0][0])
print("Distance of 1st neighbour of vertex 1:",p[1][0][1])
X = [1]
Y = [1]
A = {}
A[1] = 0
for i in range(2,201):
A[i] = 100000000
Y.append(i)
while X != Y:
b = {}
for eachvertex in X:
b2 = 0
for eachneighbour in p[eachvertex]:
if eachneighbour[0] not in X:
b2 = A[eachvertex]+eachneighbour[1]
b[eachneighbour[0]] = b2
vertex_to_be_added = min(b, key = b.get)
X.append(vertex_to_be_added)
A[vertex_to_be_added] = min(b.values())
print("Vertex added :",vertex_to_be_added, "and distance :",min(b.values()))
X.sort()
The data source can be found here : LinkToData
It works for the first iteration of the while loop, but after that the distances calculated for subsequent nodes/vertices added are not the shortest distance. Where am I going wrong ?