def BFS(map_dict, start, end, verbose):
    """
    BFS algorithm to find the shortest path between the start and end points
    on the map, following the map given by map_dict
    
    If an invalid end location is given then it will return the longest possible
    path and its length.
    
    Returns the length of the shortest route, and the overall path.
    """
    
    initPath = [start]
    pathQueue = [initPath]
    
    longest = 0
    longest_path = []
    
    moves = {1:(0,1), 2:(0,-1), 3:(-1, 0), 4:(1,0)}
      
    
    while len(pathQueue) != 0:
        # Get and remove oldest element of path queue:
        tmpPath = pathQueue.pop(0)
        
        if verbose:
            print('Current BFS path: ', tmpPath)
        lastNode = tmpPath[-1]
        
        if len(tmpPath) > longest:
            longest = len(tmpPath)
            longest_path = tmpPath    
        
        # If the last node in the path is the end, shortest route found
        if lastNode == end:
            return tmpPath, len(tmpPath)
        # Otherwise add all new possible paths to path queue:
        for i in range(1,5,1):
            dx, dy = moves[i]
            pos_x, pos_y = lastNode
            testpos = (pos_x + dx, pos_y + dy)
            # Check if legit path and not backtracking
            if map_dict[testpos] > 0 and testpos not in tmpPath:
                newPath = tmpPath + [testpos]
                pathQueue.append(newPath)
                
    # If no path found return longest path:
    return longest_path, longest