DIFFICULTY:
=
Medium
PREREQUISITES:
=
Math, Backtracking, Graph
PROBLEM:
=
The aim is to find the path between two numbers x and y such that path between x and y is as short as possible.
Quick Explanation:
=
Convert all the inputs in the form of graph & use backtracking algorithm to find shortest path from one node to another.
EXPLANATION:
================
This problem can be easily solved with the method of graph. For that, we need to convert all the input sets which are in list format to graph format:
for i in range(len(numbers)):
graph[numbers[i]] = []
for j in range(n):
for k in range(len(groups[j])):
if numbers[i] in groups[j] and groups[j][k] != numbers[i] and groups[j][k] not in graph[numbers[i]]:
graph[numbers[i]].append(groups[j][k])
Above code traverses each number one by one from start to end of each list. It will maintain a dictionary with all the unique numbers from the input to create graph. If a particular number is present with the certain key of a graph then it will add that number to the value of that key.
Let’s write a simple function to determine a path between two nodes. It takes a graph and the start and end nodes as arguments. It will return a list of nodes (including the start and end nodes) comprising the path. When no path can be found, it returns None. The same node will not occur more than once on the path returned (i.e. it won’t contain cycles). The algorithm uses an important technique called backtracking: it tries each possibility in turn until it finds a solution.
def find_path(graph, start, end, path=[]):
path = path + [start]
if start == end:
return path
if not graph.has_key(start):
return None
for node in graph[start]:
if node not in path:
newpath = find_path(graph, node, end, path)
if newpath: return newpath
return None
The second ‘if’ statement is necessary only in case there are nodes that are listed as end points for arcs but that don’t have outgoing arcs themselves, and aren’t listed in the graph at all. Such nodes could also be contained in the graph, with an empty list of outgoing arcs, but sometimes it is more convenient not to require this.