Where am I going wrong in Dijkstra's implementation for shortest distance from source

Viewed 54

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 ?

0 Answers
Related