def bruteForceSearch(graph,start,end,maxTotalDist,maxDistOutdoors,visited = [],dist =0,outDist = 0):
"""
Finds the shortest path from start to end using brute-force approach.
The total distance travelled on the path must not exceed maxTotalDist, and
the distance spent outdoor on this path must not exceed maxDisOutdoors.
Parameters:
digraph: instance of class Digraph or its subclass
start, end: start & end building numbers (strings)
maxTotalDist : maximum total distance on a path (integer)
maxDistOutdoors: maximum distance spent outdoors on a path (integer)
Assumes:
start and end are numbers for existing buildings in graph
Returns:
The shortest-path from start to end, represented by
a list of building numbers (in strings), [n_1, n_2, ..., n_k],
where there exists an edge from n_i to n_(i+1) in digraph,
for all 1 <= i < k.
If there exists no path that satisfies maxTotalDist and
maxDistOutdoors constraints, then raises a ValueError.
"""
path = [str(start)]
pathDist = [str(dist)]
pathOut = [str(outDist)]
if MITNode(start) == MITNode(end):
return path, dist,outDist
shortest = None
if visited == []:
visited = [str(start)]
for edge in graph.childrenOf(MITNode(start)):
if str(edge.getDestination()) not in visited:
visited = visited + [str(edge.getDestination())]
possPath, possDist,possOutDist = bruteForceSearch(graph,edge.getDestination(),\
end,maxTotalDist,maxDistOutdoors,visited, edge.getDistance(),edge.getOutDist())
if possPath == None:
continue
if maxDistOutdoors == 0:
if possOutDist != 0:
continue
if shortest == None or possDist < bestDist:
shortest = possPath
bestDist = possDist
bestOutDist = possOutDist
if shortest == None:
path = None
retPathDist = [str(0)]
retOutDist = [str(0)]
elif (dist + bestDist) > maxTotalDist or (outDist + bestOutDist) > maxDistOutdoors:
path = None
retPathDist = [str(0)]
retOutDist = [str(0)]
else:
path = path + shortest
retPathDist = dist + bestDist
retOutDist = outDist + bestOutDist
return path, retPathDist,retOutDist