Solution for Data Dog challenge

datadog_challenge.py

# Source: https://www.geeksforgeeks.org/find-paths-given-source-destination/
# Modified by Dainius

from collections import defaultdict

class Graph:
    """
    Represents undirected graph.
    """

    def __init__(self):
        self.graph = defaultdict(list)
        self.distances = dict()
        self.paths = []

    def add_edge(self, u, v, w):
        """
        Add weighted edge to graph.
        :param u: from node
        :param v: to node
        :param w: weight
        """
        self.graph[u].append(v)
        self.graph[v].append(u)

        self.distances[(u, v)] = w
        self.distances[(v, u)] = w


    def print_all_paths_util(self, u, d, visited, path):
        """
        A recursive function to print all paths from 'u' to 'd'.
        :param u: from node
        :param d: destination node
        :param visited: keeps track of vertices in current path.
        :param path: stores actual vertices and path_index is current
        """

        # Mark the current node as visited and store in path 
        visited[u] = True
        path.append(u)

        # If current vertex is same as destination, then save current path
        if u == d:
            distance = 0
            # Calculate distance
            for i, i_next in zip(path, path[1:]):
                distance += self.distances[(i, i_next)]

            self.paths.append({'path': path.copy(), 'distance': distance})
        # If current vertex is not destination recur for all the vertices adjacent to this vertex
        else:
            for i in self.graph[u]:
                if not visited[i]:
                    self.print_all_paths_util(i, d, visited, path)

        # Remove current vertex from path[] and mark it as unvisited
        path.pop()
        visited[u] = False

    def get_all_paths(self, source, destination):
        # Mark all the vertices as not visited 
        visited = {}
        for k in self.graph.keys():
            visited[k] = False

        # Create an array to store paths
        path = []
        # Call the recursive helper function to print all paths 
        self.print_all_paths_util(source, destination, visited, path)
        return self.paths


# Create graph
g = Graph()
g.add_edge('Kaunas0', 'No_Name', 110)
g.add_edge('Kaunas0', 'Jurbarkas', 88)
g.add_edge('Kaunas0', 'Marijampolė', 62)
g.add_edge('Kaunas0', 'Prienai', 39)
g.add_edge('Kaunas0', 'Vilnius', 104)
g.add_edge('Kaunas0', 'Ukmergė', 70)
g.add_edge('Kaunas0', 'Kėdainiai', 53)

g.add_edge('Kaunas1', 'No_Name', 110)
g.add_edge('Kaunas1', 'Jurbarkas', 88)
g.add_edge('Kaunas1', 'Marijampolė', 62)
g.add_edge('Kaunas1', 'Prienai', 39)
g.add_edge('Kaunas1', 'Vilnius', 104)
g.add_edge('Kaunas1', 'Ukmergė', 70)
g.add_edge('Kaunas1', 'Kėdainiai', 53)

g.add_edge('No_Name', 'Klaipėda', 106)
g.add_edge('No_Name', 'Pagėgiai', 66)
g.add_edge('No_Name', 'Jurbarkas', 50)
g.add_edge('No_Name', 'Šiauliai', 68)

g.add_edge('Klaipėda', 'Palanga', 30)
g.add_edge('Klaipėda', 'Pagėgiai', 88)

g.add_edge('Palanga', 'Šiauliai', 120)

g.add_edge('Pagėgiai', 'Jurbarkas', 59)

g.add_edge('Jurbarkas', 'Marijampolė', 90)

g.add_edge('Marijampolė', 'Prienai', 41)
g.add_edge('Marijampolė', 'Alytus', 63)

g.add_edge('Alytus', 'Prienai', 33)
g.add_edge('Alytus', 'Varėna', 48)

g.add_edge('Varėna', 'Vilnius', 82)

g.add_edge('Prienai', 'Vilnius', 96)

g.add_edge('Vilnius', 'Ukmergė', 73)
g.add_edge('Vilnius', 'Utena', 97)

g.add_edge('Ukmergė', 'Kėdainiai', 59)
g.add_edge('Ukmergė', 'Utena', 64)

g.add_edge('Utena', 'Panevėžys', 103)

g.add_edge('Panevėžys', 'Ukmergė', 69)
g.add_edge('Panevėžys', 'Kėdainiai', 64)
g.add_edge('Panevėžys', 'Šeduva', 43)

g.add_edge('Šeduva', 'Šiauliai', 39)
g.add_edge('Šeduva', 'Kėdainiai', 58)


source = 'Kaunas0'
destination = 'Kaunas1'

all_paths = g.get_all_paths(source, destination)

# Sort by distance and then by amount of nodes
all_paths.sort(key=lambda x: (x['distance'], len(x['path'])))

# Write to text file all paths
f = open('results.txt', 'w+', encoding='utf8')
for i in all_paths:
    path_friendly = ' -> '.join(i['path'])
    f.write('Distance: {0}. Cities visited: {1}. Path: {2}\n'.format(i['distance'], len(i['path']) - 2, path_friendly))
f.close()

results.txt

...
Distance: 750. Cities visited: 8. Path: Kaunas0 -> No_Name -> Klaipėda -> Pagėgiai -> Jurbarkas -> Marijampolė -> Alytus -> Varėna -> Vilnius -> Kaunas1
Distance: 750. Cities visited: 8. Path: Kaunas0 -> Vilnius -> Varėna -> Alytus -> Marijampolė -> Jurbarkas -> Pagėgiai -> Klaipėda -> No_Name -> Kaunas1
Distance: 750. Cities visited: 10. Path: Kaunas0 -> No_Name -> Šiauliai -> Šeduva -> Kėdainiai -> Ukmergė -> Utena -> Vilnius -> Varėna -> Alytus -> Marijampolė -> Kaunas1
Distance: 750. Cities visited: 10. Path: Kaunas0 -> Marijampolė -> Alytus -> Varėna -> Vilnius -> Utena -> Ukmergė -> Kėdainiai -> Šeduva -> Šiauliai -> No_Name -> Kaunas1
Distance: 750. Cities visited: 10. Path: Kaunas0 -> Vilnius -> Prienai -> Marijampolė -> Jurbarkas -> Pagėgiai -> No_Name -> Šiauliai -> Šeduva -> Kėdainiai -> Ukmergė -> Kaunas1
Distance: 750. Cities visited: 10. Path: Kaunas0 -> Ukmergė -> Kėdainiai -> Šeduva -> Šiauliai -> No_Name -> Pagėgiai -> Jurbarkas -> Marijampolė -> Prienai -> Vilnius -> Kaunas1
Distance: 750. Cities visited: 11. Path: Kaunas0 -> No_Name -> Jurbarkas -> Marijampolė -> Prienai -> Alytus -> Varėna -> Vilnius -> Ukmergė -> Panevėžys -> Šeduva -> Kėdainiai -> Kaunas1
Distance: 750. Cities visited: 11. Path: Kaunas0 -> Prienai -> Marijampolė -> Jurbarkas -> No_Name -> Pagėgiai -> Klaipėda -> Palanga -> Šiauliai -> Šeduva -> Kėdainiai -> Ukmergė -> Kaunas1
Distance: 750. Cities visited: 11. Path: Kaunas0 -> Prienai -> Marijampolė -> Jurbarkas -> Pagėgiai -> No_Name -> Klaipėda -> Palanga -> Šiauliai -> Šeduva -> Panevėžys -> Kėdainiai -> Kaunas1
Distance: 750. Cities visited: 11. Path: Kaunas0 -> Prienai -> Alytus -> Marijampolė -> Jurbarkas -> No_Name -> Šiauliai -> Šeduva -> Kėdainiai -> Panevėžys -> Ukmergė -> Vilnius -> Kaunas1
Distance: 750. Cities visited: 11. Path: Kaunas0 -> Vilnius -> Ukmergė -> Panevėžys -> Kėdainiai -> Šeduva -> Šiauliai -> No_Name -> Jurbarkas -> Marijampolė -> Alytus -> Prienai -> Kaunas1
Distance: 750. Cities visited: 11. Path: Kaunas0 -> Ukmergė -> Kėdainiai -> Šeduva -> Šiauliai -> Palanga -> Klaipėda -> Pagėgiai -> No_Name -> Jurbarkas -> Marijampolė -> Prienai -> Kaunas1
Distance: 750. Cities visited: 11. Path: Kaunas0 -> Kėdainiai -> Panevėžys -> Šeduva -> Šiauliai -> Palanga -> Klaipėda -> No_Name -> Pagėgiai -> Jurbarkas -> Marijampolė -> Prienai -> Kaunas1
Distance: 750. Cities visited: 11. Path: Kaunas0 -> Kėdainiai -> Šeduva -> Panevėžys -> Ukmergė -> Vilnius -> Varėna -> Alytus -> Prienai -> Marijampolė -> Jurbarkas -> No_Name -> Kaunas1
Distance: 750. Cities visited: 12. Path: Kaunas0 -> Jurbarkas -> No_Name -> Šiauliai -> Šeduva -> Panevėžys -> Kėdainiai -> Ukmergė -> Vilnius -> Varėna -> Alytus -> Prienai -> Marijampolė -> Kaunas1
Distance: 750. Cities visited: 12. Path: Kaunas0 -> Marijampolė -> Jurbarkas -> No_Name -> Šiauliai -> Šeduva -> Panevėžys -> Kėdainiai -> Ukmergė -> Vilnius -> Varėna -> Alytus -> Prienai -> Kaunas1
Distance: 750. Cities visited: 12. Path: Kaunas0 -> Marijampolė -> Prienai -> Alytus -> Varėna -> Vilnius -> Ukmergė -> Kėdainiai -> Panevėžys -> Šeduva -> Šiauliai -> No_Name -> Jurbarkas -> Kaunas1
Distance: 750. Cities visited: 12. Path: Kaunas0 -> Prienai -> Alytus -> Varėna -> Vilnius -> Ukmergė -> Kėdainiai -> Panevėžys -> Šeduva -> Šiauliai -> No_Name -> Jurbarkas -> Marijampolė -> Kaunas1
...