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 = { 'Arad': ['Zerind', 'Timisoara', 'Sibiu'], 'Bucharest': ['Urziceni', 'Giurgiu', 'Pitesti', 'Fagaras'], 'Craiova': ['Dobreta', 'Pitesti', 'Rimnicu Vilcea'], 'Dobreta': ['Mehadia', 'Craiova'], 'Eforie': ['Hirsova'], 'Fagaras': ['Sibiu', 'Bucharest'], 'Giurgiu': ['Bucharest'], 'Hirsova': ['Eforie', 'Urziceni'], 'Iasi': ['Neamt', 'Vaslui'], 'Lugoj': ['Mehadia', 'Timisoara'], 'Mehadia': ['Lugoj', 'Dobreta'], 'Neamt': ['Iasi'], 'Oradea': ['Zerind', 'Sibiu'], 'Pitesti': ['Rimnicu Vilcea', 'Bucharest', 'Craiova'], 'Rimnicu Vilcea': ['Sibiu', 'Pitesti', 'Craiova'], 'Sibiu': ['Rimnicu Vilcea', 'Fagaras', 'Arad', 'Oradea'], 'Timisoara': ['Lugoj', 'Arad'], 'Urziceni': ['Bucharest', 'Hirsova'], 'Vaslui': ['Iasi', 'Urziceni'], 'Zerind': ['Oradea', 'Arad'] } # Function Call BFS_SP(graph, 'Arad', 'Bucharest')

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]], 'Dobreta': [['Mehadia', 75], ['Craiova', 120]], 'Eforie': [['Hirsova', 86]], 'Fagaras': [['Sibiu', 99], ['Bucharest', 211]], 'Giurgiu': [['Bucharest', 90]], 'Hirsova': [['Eforie', 86], ['Urziceni', 98]], 'Iasi': [['Neamt', 87], ['Vaslui', 92]], 'Lugoj': [['Mehadia', 70], ['Timisoara', 111]], 'Mehadia': [['Lugoj', 70], ['Dobreta', 75]], 'Neamt': [['Iasi', 87]], 'Oradea': [['Zerind', 71], ['Sibiu', 151]], 'Pitesti': [['Rimnicu Vilcea', 97], ['Bucharest', 101], ['Craiova', 138]], 'Rimnicu Vilcea': [['Sibiu', 80], ['Pitesti', 97], ['Craiova', 146]], 'Sibiu': [['Rimnicu Vilcea', 80], ['Fagaras', 99], ['Arad', 140], ['Oradea', 151]], 'Timisoara': [['Lugoj', 111], ['Arad', 118]], 'Urziceni': [['Bucharest', 85], ['Hirsova', 98]], 'Vaslui': [['Iasi', 92], ['Urziceni', 142]], 'Zerind': [['Oradea', 71], ['Arad', 75]] }

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> BFS_SP(graph, 'Arad', 'Bucharest') 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!!

## Answer

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`

.