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: interview

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    #using dijkstra
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 = {}; #node name, node path
    boarderNodes = {startPoint:{'path': [[startPoint]], 'cost':0}}; #node name, node path, node cost
    
    #do greedy first search
    #loop while boarder not empty
    while(len(boarderNodes)>0):
        #expand unknown node with lowest cost
        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]
        
        # add to boarder at right spot/ update cost values if necessary
        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)
        
        # goal check -> is goal in visited Nodes
        if endPoint in visitedNodes:
            return visitedNodes[endPoint];
        
        #EndLoop

    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):
    '''
    Problem description: https://www.codewars.com/kata/5709aa85fe2d012f1d00169c/train/python
    Made intentionally with 2 classes: PathFinder and TimeFinder
    For simulating real-life project structure, covering unittests, multiprocessing etc.
    '''

    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):
        '''Computes time for given path after its validated in PathFinder'''
        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):
        '''
        1. Return list of lists containing waypoints
        2. If 2 paths are equally time consuming, then pick the one with fewer waypoints
        3. If there are still multiple solutions complying with 2nd requirement, sort them in alphabetical order
        '''
        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)