# BFS search algorithm

I am newly learning Python, and I am trying to create a bfs algorithm that can take vertices of a weighted graph and return the bfs. Eventually, I will need to add the weighted edges to the vertices so that I can calculate the distance travelled, however I am able to get the bfs to work with my vertices alone. This is the code so far:

```# Python implementation to find the
# shortest path in the graph using
# dictionaries

# Function to find the shortest
# path between two nodes of a graph
def BFS_SP(graph, start, goal):

explored = []

# Queue for traversing the
# graph in the BFS
queue = [[start]]

# If the desired node is
# reached
if start == goal:
print("Same Node")
return

# Loop to traverse the graph
# with the help of the queue
while queue:
path = queue.pop(0)
node = path[-1]

# Condition to check if the
# current node is not visited
if node not in explored:
neighbours = graph[node]

# Loop to iterate over the
# neighbours of the node
for neighbour in neighbours:
new_path = list(path)
new_path.append(neighbour)
queue.append(new_path)

# Condition to check if the
# neighbour node is the goal
if neighbour == goal:
print("Shortest path = ", *new_path)
return
explored.append(node)

# Condition when the nodes
# are not connected
print("So sorry, but a connecting"
" path doesn't exist :(")
return
# Driver Code
if __name__ == "__main__":

# Graph using dictionaries
graph = {
'Bucharest':        ['Urziceni', 'Giurgiu', 'Pitesti', 'Fagaras'],
'Craiova':          ['Dobreta', 'Pitesti', 'Rimnicu Vilcea'],
'Eforie':           ['Hirsova'],
'Fagaras':          ['Sibiu', 'Bucharest'],
'Giurgiu':          ['Bucharest'],
'Hirsova':          ['Eforie', 'Urziceni'],
'Iasi':             ['Neamt', 'Vaslui'],
'Neamt':            ['Iasi'],
'Pitesti':          ['Rimnicu Vilcea', 'Bucharest', 'Craiova'],
'Rimnicu Vilcea':   ['Sibiu', 'Pitesti', 'Craiova'],
'Urziceni':         ['Bucharest', 'Hirsova'],
'Vaslui':           ['Iasi', 'Urziceni'],
}

# Function Call
```

I need my graph array to actually look like this instead:

```graph = {
'Arad':             [['Zerind', 75], ['Timisoara', 118], ['Sibiu', 140]],
'Bucharest':        [['Urziceni', 85], ['Giurgiu', 90], ['Pitesti', 101], ['Fagaras', 211]],
'Craiova':          [['Dobreta', 120], ['Pitesti', 138], ['Rimnicu Vilcea', 146]],
'Eforie':           [['Hirsova', 86]],
'Fagaras':          [['Sibiu', 99], ['Bucharest', 211]],
'Giurgiu':          [['Bucharest', 90]],
'Hirsova':          [['Eforie', 86], ['Urziceni', 98]],
'Iasi':             [['Neamt', 87], ['Vaslui', 92]],
'Neamt':            [['Iasi', 87]],
'Pitesti':          [['Rimnicu Vilcea', 97], ['Bucharest', 101], ['Craiova', 138]],
'Rimnicu Vilcea':   [['Sibiu', 80], ['Pitesti', 97], ['Craiova', 146]],
'Urziceni':         [['Bucharest', 85], ['Hirsova', 98]],
'Vaslui':           [['Iasi', 92], ['Urziceni', 142]],
}
```

And I’m some what of a loss on how I can modify my code to take the new version of graph as individual nodes. If I implement my new graph as I need it into my old code, I receive an error that say:

```Traceback (most recent call last):
File "/Users/meikebuettner/hello/astar_test.py", line 79, in <module>
File "/Users/meikebuettner/hello/astar_test.py", line 30, in BFS_SP
neighbours = graph[node]
TypeError: unhashable type: 'list'
```

Any insight, help, idea or topic to research would be GREATLY appreciated! Thank you!!

The problem was caused by you adding nodes, which is a list in your new data structure, to `new_path`

```for neighbour in neighbours: # neighbour: ['Rimnicu Vilcea', 97]
...
new_path.append(neighbour)
```

`new_path` is expected to contain only the names of the nodes, not names and weights.

We can fix as:

```for neighbour_node in neighbours:
neighbour = neighbour_node[0]
...
```

Reasons for this suggestion:

• `neighbour_node` is more correct name than neighbour in this case because it represents the node, not the name of the neigbour.
• We can fix the comparison for neighbour and goal without modifying that line
```# Condition to check if the
# neighbour node is the goal
if neighbour == goal:
```

Note: there are several ways to fix your code, mine is just one. You can try the others like changing the data structure of `path` and `new_path`.