Best First Search BFS

# -*- coding: utf-8 -*-
"""
Created on Sun Feb 23 00:23:50 2020

@author: Faisal Ahmed
"""

graph = {"Oradea":{"Zerind":71,"Sibiu":151},
         "Zerind":{"Oradea":71,"Arad":75},
         "Arad":{"Zerind":75,"Timisoara":118,"Sibiu":140},
         "Timisoara":{"Arad":118,"Lugoj":111},
         "Lugoj":{"Timisoara":111,"Mehadia":70},
         "Mehadia":{"Lugoj":70,"Dobreta":75},
         "Dobreta":{"Mehadia":75,"Craiova":120},
         "Craiova":{"Dobreta":120,"Rimnicu Vilcea":146,"Pitesti":138},
         "Sibiu":{"Arad":140,"Oradea":151,"Rimnicu Vilcea":80,"Fagaras":99},
         "Rimnicu Vilcea":{"Sibiu":80,"Craiova":146,"Pitesti":97},
         "Fagaras":{"Sibiu":99,"Bucharest":211},
         "Pitesti":{"Bucharest":101,"Rimnicu Vilcea":97,"Craiova":138},
         "Bucharest":{"Fagaras":211,"Pitesti":101,"Giurgiu":90,"Urziceni":85},
         "Giurgiu":{"Bucharest":90},"Urziceni":{"Bucharest":85,"Hirsova":98,"Vaslui":142},
         "Hirsova":{"Urziceni":98,"Eforie":86},
         "Eforie":{"Hirsova":86},
         "Vaslui":{"Urziceni":142,"Iasi":92},
         "Iasi":{"Vaslui":92,"Neamt":87},
         "Neamt":{"Iasi":87}
}

start='Arad'
goal='Bucharest'
fringe=[]
parent={}
visited=[]

fringe.append(start)
visited.append(start)
parent[start]=None
found=False

while len(fringe)>0:
    u=fringe[0]
    del fringe[0]
    adjDict=graph[u]

    for v in adjDict.keys():
        if v not in parent:
            parent[v]=u
            if v==goal:
                found=True
                break
        fringe.append(v)
    if found:
        break


current=goal
path=[]
distance=0

path.append(current)
while parent[current]!=None:
    path.append(parent[current])
    distance=distance+graph[current][parent[current]]
    current=parent[current]

path.reverse()

print("Path : ")
for i in path:
    print(i,end=" ")

print("\nDistance : ",distance)