The professional Russian, Dmitri, from the popular youtube channel FPSRussia has hired you to help him move his arms cache between locations without detection by the authorities.  Your job is to write a Shortest Path First (SPF) algorithm that will provide a route with the shortest possible travel time between waypoints, which will minimize the chances of detection.  One exception is that you can't travel through the same waypoint twice.  Once you've been seen there is a higher chance of detection if you travel through that waypoint a second time.

Your function shortestPath will take three inputs, a topology/map of the environment, along with a starting point, and an ending point.  The topology will be a dictionary with the keys being the different waypoints.  The values of each entry will be another dictionary with the keys being the adjacent waypoints, and the values being the time it takes to travel to that waypoint.

Take the following topology as an example:

     topology = {'a' : {'b': 10, 'c': 20},
                 'b' : {'a': 10, 'c': 20},
                 'c' : {'a': 10, 'b': 20} }

In this example, waypoint 'a' has two adjacent waypoints, 'b' and 'c'.  And the time it takes to travel from 'a' to 'b' is 10 minutes, and from 'a' to 'c' is 20 minutes.  It's important to note that the time between these waypoints is one way travel time and can be different in opposite directions.  This is highlighted in the example above where a->c takes 20 minutes, but c->a takes 10 minutes.

The starting and ending points will passed to your function as single character strings such as 'a' or 'b', which will match a key in your topology.

The return value should be in the form of a list of lists of waypoints that make up the shortest travel time.  If there multiple paths that have equal travel time, then you should choose the path with the least number of waypoints.  If there are still multiple paths with equal travel time and number of waypoints, then you should return a list of lists with the multiple options. For multiple solutions, the list of paths should be sorted in lexicographic (alphabetical) order. If there is only one shortest path, you should still return a list of that list.

Here are a few examples:
    #Topology
    #      b--d--g   
    #     /   |   \  
    #    /    |    \ 
    #   a-----e     h
    #    \     \   / 
    #     \     \ /  
    #      c-----f  
    topology = {'a' : {'b': 10, 'c': 20, 'e':20},
                'b' : {'a': 10, 'd': 20},
                'c' : {'a': 10, 'f': 20},
                'd' : {'b': 10, 'e': 20, 'g': 20},
                'e' : {'a': 10, 'd': 20, 'f': 20},                      
                'f' : {'c': 10, 'e': 20, 'h': 20},
                'g' : {'d': 10, 'h': 20},
                'h' : {'g': 10, 'f': 20},
    }
    
    Two solutions with a time of 40:
    shortestPath(topology, 'a', 'f') == [['a', 'c', 'f'], ['a', 'e', 'f']] 
     
    One solution with a time of 20:
    shortestPath(topology, 'a', 'e') == [['a', 'e']]

Difficulty: MEDIUM_HARD

Starter code:
def shortestPath(topology, startPoint, endPoint):
	

Solutions:
from collections import defaultdict

def shortestPath(gra, srs, des):
	(Q, paths, d) = ([[0, srs]], [], defaultdict(list))
	while Q:
		vrt = Q.pop(0)
		if vrt[-1] == des:
			paths.append(vrt)
			continue
		for (v, c) in gra[vrt[-1]].items():
			if v not in vrt:
				Q.append([vrt[0] + c] + vrt[1:] + [v])
	for i in paths:
		d[i[0]].append(i[1:])
	(ml, f) = (len(min(d[min(d)], key=len)), [])
	for i in d[min(d)]:
		if len(i) == ml:
			f.append(i)
	return [sorted(i) for i in f] if len(f) > 2 else f


def shortestPath(topology, startPoint, endPoint):
	(stack, shortest, paths) = ([(1, [startPoint])], float('inf'), [])
	while stack:
		(acc, path) = stack.pop()
		point = path[-1]
		if point == endPoint:
			if acc <= shortest:
				paths.append((acc, path))
				shortest = acc
			continue
		points = topology.get(point)
		for p in points:
			if p not in path:
				stack.append((acc + points[p] + 1, path + [p]))
	return sorted([path for (val, path) in paths if val == shortest])


from heapq import heappush as push, heappop as pop

def shortestPath(topology, startPoint, endPoint):
	(current, res) = ([], (float('inf'), None, []))
	push(current, (0, 1, [startPoint]))
	while current:
		(time, size, path) = pop(current)
		if time > res[0] or (time == res[0] and size > res[1]):
			return res[2]
		if path[-1] == endPoint:
			if time < res[0] or size < res[1]:
				res = (time, size, [path])
			else:
				res[2].append(path)
		else:
			for (k, v) in topology[path[-1]].items():
				if k not in path:
					push(current, (time + v, size + 1, path + [k]))
	return 'No path'


from collections import defaultdict, deque

def shortestPath(topology, start, end):
	vertices = defaultdict(list)
	(edges, distance_, parent_) = ({}, {}, {})
	for (i, j) in topology.items():
		distance_[i] = float('inf')
		parent_[i] = None
		for (k, l) in j.items():
			vertices[i].append(k)
			edges[i, k] = l
	distance_[start] = 0
	Q = deque([[(start, 0), distance_, parent_]])
	(pairs, PATHS) = (set(), set())
	while Q:
		((node, cost), distance, parent) = Q.popleft()
		while distance:
			if node == end:
				break
			for neighbour in vertices[node]:
				if neighbour in distance:
					dis = cost + edges[node, neighbour]
					if dis < distance[neighbour]:
						distance[neighbour] = dis
						parent[neighbour] = node
			del distance[node]
			(node, cost) = min(distance.items(), key=lambda x: x[1])
			for (i, j) in distance.items():
				if (i, node) not in pairs and j == cost and (i != node):
					pairs.add((i, node))
					Q.append([(i, j), distance.copy(), parent.copy()])
		(path, node) = ([], end)
		while node != start:
			path.insert(0, node)
			node = parent[node]
		PATHS.add((start,) + tuple(path))
	return sorted(list(map(list, PATHS)))


import queue

def shortestPath(topology, startPoint, endPoint):
	q = queue.Queue()
	q.put([startPoint, [startPoint], 0])
	routes = []
	while not q.empty():
		(current_node, path, cost) = q.get()
		if current_node == endPoint:
			routes.append((path, cost))
		for (point, distance) in list(topology[current_node].items()):
			new_path = path.copy()
			if point not in path:
				new_path += [point]
				q.put([point, new_path, cost + topology[current_node][point]])
	lowest_cost = min(routes, key=lambda x: x[1])
	other_lowest_cost = [x[0] for x in routes if x[1] == lowest_cost[1] and len(x[0]) == len(lowest_cost[0])]
	return other_lowest_cost


def shortestPath(topology, startPoint, endPoint):
	print(topology)
	print(startPoint)
	print(endPoint)
	visitedNodes = {}
	boarderNodes = {startPoint: {'path': [[startPoint]], 'cost': 0}}
	while len(boarderNodes) > 0:
		cost = None
		node = ''
		for (boarderNodeName, boarderNodeDict) in list(boarderNodes.items()):
			if cost == None:
				node = boarderNodeName
				cost = boarderNodeDict['cost']
			elif boarderNodeDict['cost'] < cost:
				node = boarderNodeName
				cost = boarderNodeDict['cost']
		path = boarderNodes[node]['path']
		visitedNodes[node] = path
		del boarderNodes[node]
		for (neighborNode, neighborCost) in list(topology[node].items()):
			if not neighborNode in visitedNodes and (not neighborNode in boarderNodes):
				boarderNodes[neighborNode] = {'path': [[]], 'cost': cost + neighborCost}
				addPath(boarderNodes, neighborNode, path)
			elif not neighborNode in visitedNodes and neighborNode in boarderNodes:
				if boarderNodes[neighborNode]['cost'] > cost + neighborCost:
					boarderNodes[neighborNode]['cost'] = cost + neighborCost
					boarderNodes[neighborNode]['path'] = [[]]
					addPath(boarderNodes, neighborNode, path)
				elif boarderNodes[neighborNode]['cost'] == cost + neighborCost:
					mergePath(boarderNodes, neighborNode, path, topology)
		if endPoint in visitedNodes:
			return visitedNodes[endPoint]
	return 0

def addPath(boarderNodes, neighborNode, path):
	boarderNodes[neighborNode]['path'] = []
	for i in path:
		line = []
		for j in i:
			line.append(j)
		line.append(neighborNode)
		boarderNodes[neighborNode]['path'].append(line)

def mergePath(boarderNodes, neighborNode, path, topology):
	smallest = len(topology)
	for i in path:
		if len(i) + 1 < smallest:
			smallest = len(i) + 1
	for i in boarderNodes[neighborNode]['path']:
		if len(i) < smallest:
			smallest = len(i)
	for i in path:
		line = []
		for j in i:
			line.append(j)
		line.append(neighborNode)
		boarderNodes[neighborNode]['path'].append(line)
	for i in boarderNodes[neighborNode]['path']:
		if len(i) > smallest:
			boarderNodes[neighborNode]['path'].remove(i)


def shortestPath(topology, startPoint, endPoint):

	class PathFinder:

		def __init__(self, topology, start_point, end_point):
			self.start_point = start_point
			self.end_point = end_point
			self.tplg = topology
			self.next_step = None
			self.considered_path = None
			self.backtrack = [{self.start_point: [*self.tplg[self.start_point].keys()]}]
			self.history = self.start_point
			self.finished_paths = []

		def solve(self):

			def try_forward():
				get_next_step()
				self.considered_path = self.history + self.next_step
				if self.next_step == self.end_point:
					self.finished_paths.append(self.considered_path)
					try_backward()
				elif self.next_step not in self.history:
					clean_backtrack()
					add_new_crossroad_to_backtrack()
					self.history = self.considered_path
					try_forward()
				else:
					try_backward()

			def try_backward():
				clean_backtrack()
				try_forward()

			def clean_backtrack():
				del list(self.backtrack[-1].values())[0][-1]
				directions_left_to_consider_at_last_path = list(self.backtrack[-1].values())[0]
				last_path = [*self.backtrack[-1].keys()][0]
				if not directions_left_to_consider_at_last_path and len(last_path) > 1:
					del self.backtrack[-1]
					last_path = [*self.backtrack[-1].keys()][0]
					self.history = last_path

			def add_new_crossroad_to_backtrack():
				self.backtrack.append({self.considered_path: [*self.tplg[self.next_step].keys()]})

			def get_next_step():
				self.next_step = list(self.backtrack[-1].values())[0][-1]

			def execute():
				try:
					try_forward()
				except IndexError:
					pass
			execute()
			return self.finished_paths

	def compute_path_time(path):

		def get_time(previous_step, next_step):
			return topology[previous_step][next_step]

		def get_next_pair_of_steps(path, iter_no):
			return (path[iter_no], path[iter_no + 1])
		time = 0
		for iter_no in range(len(path) - 1):
			time += get_time(*get_next_pair_of_steps(path, iter_no))
		return time
	finished_paths = PathFinder(topology, startPoint, endPoint).solve()
	path_time_dict = {path: compute_path_time(path) for path in finished_paths}

	def adjust_for_codewars_requirements(path_time_dict):
		shortest_time = min(path_time_dict.values())
		paths_with_shortest_time = [path for path in path_time_dict.keys() if path_time_dict[path] == shortest_time]
		minimum_waypoint_number = min([len(path) for path in paths_with_shortest_time])
		paths_with_minimum_waypoint_number = list(filter(lambda x: len(x) == minimum_waypoint_number, paths_with_shortest_time))
		adjusted = [[waypoint for waypoint in path] for path in sorted(paths_with_minimum_waypoint_number)]
		return adjusted
	return adjust_for_codewars_requirements(path_time_dict)


def shortestPath(topology, startPoint, endPoint):
	graph = {}
	for (key, value) in topology.items():
		values = []
		for (k, v) in value.items():
			values.append(k)
		graph[key] = values
	paths = find_all_paths(graph, startPoint, endPoint)
	if len(paths) == 0:
		return []
	pathsAndDistances = []
	for path in paths:
		distance = 0
		for (i, waypoint) in enumerate(path):
			if i < len(path) - 1:
				distance += topology[waypoint][path[i + 1]]
		pathsAndDistances.append((distance, path))
	pathsAndDistances = [t for t in pathsAndDistances if t[0] == min(pathsAndDistances)[0]]
	length = 1000
	for p in pathsAndDistances:
		if len(p[1]) < length:
			length = len(p[1])
	answer = []
	for p in pathsAndDistances:
		if len(p[1]) == length:
			answer.append(p[1])
	return answer

def find_all_paths(graph, start, end, path=[]):
	path = path + [start]
	if start == end:
		return [path]
	if start not in graph:
		return []
	paths = []
	for node in graph[start]:
		if node not in path:
			newpaths = find_all_paths(graph, node, end, path)
			for newpath in newpaths:
				paths.append(newpath)
	return paths


def find_all_paths(topology, start, end, path=[]):
	if start not in topology:
		return None
	path = path + [start]
	if start == end:
		return [path]
	paths = []
	for node in topology[start]:
		if node not in path:
			e_path = find_all_paths(topology, node, end, path)
			for p in e_path:
				paths.append(p)
	return paths

def distance(topology):
	dist = {}
	for element in topology:
		for node in topology[element]:
			dist[element, node] = topology[element][node]
	return dist

def calculate_path_distance(path, distances):
	path_dic = {}
	for p in path:
		d = 0
		for i in range(0, len(p) - 1):
			d = d + distances[tuple(p[i:i + 2])]
		path_dic[tuple(p)] = d
	return path_dic

def calculate_short_distance(paths_with_distance):
	shortest = []
	multiple_opt = {}
	shortest_opt = []
	values = sorted(paths_with_distance.values())
	for item in list(paths_with_distance.items()):
		if item[1] == values[0]:
			shortest.append(list(item[0]))
	if len(shortest) > 1:
		for i in shortest:
			multiple_opt[tuple(i)] = len(i)
		options = sorted(multiple_opt.values())
		for e in list(multiple_opt.items()):
			if e[1] == options[0]:
				shortest_opt.append(list(e[0]))
		shortest_opt.sort()
		return shortest_opt
	return shortest

def shortestPath(topology, start, end):
	path = find_all_paths(topology, start, end)
	distances = distance(topology)
	path_d = calculate_path_distance(path, distances)
	return calculate_short_distance(path_d)