from collections import deque, namedtuple

class Path:
    def __init__(self, distance, previous):
        self.distance = distance
        self.previous = previous
    def __str__(self):
        return str([self.distance, self.previous])
    def __repr__(self):
        return str([self.distance, self.previous])


inf = float('inf')
Edge = namedtuple('Edge','start, end, cost')

def make_edge(start, end, cost = 1):
    return Edge(start,end,cost)

class Graph:
    def __init__(self,edges):
        self.edges = []
        for edge in edges:
            self.edges.append(make_edge(*edge))

    @property
    def vertices(self):
        x = set() #unordered unique list {}
        #sum(([edge.start, edge.end] for edge in self.edges), [])
        for edge in self.edges:
            x.add(edge.start)
            x.add(edge.end)
        return  x

    # def getEdge(self, n1, n2):
    #     A = [[n1,n2],[n2,n1]]
    #     for edge in self.edges:
    #         if [edge.start, edge.end] in A:
    #             return edge
    #     return None
    # def remove_edge(self, n1, n2):
    #     edge = self.getEdge(n1,n2)
    #     if edge is not None:
    #         self.edges.remove(edge)
    # def add_edge(self, n1, n2, cost =1):
    #     edge = self.getEdge(n1,n2)
    #     print(edge)
    #     if edge is not None:
    #         return ValueError('Edge {} {} already exists'.format(n1,n2))
    #     self.edges.append(Edge(start = n1, end = n2, cost = cost))

    def getNeighbours(self, vertex):
        neighbours = {}
        for edge in self.edges:
            if edge.start == vertex:
                neighbours[edge.end] = edge.cost
            elif edge.end == vertex:
                neighbours[edge.start] = edge.cost
        return neighbours

    def dijkstra(self, source, dest):

        paths = {}
        unvisited = []
        for vertex in self.vertices:
            paths[vertex] = Path(inf,None)
            unvisited.append(vertex)
        paths[source].distance = 0
        currentVertex = source
        while unvisited:
            neighbours = self.getNeighbours(currentVertex)

            nextVertex = None
            nextVertexCost = inf
            for neighbour, edgeCost in neighbours.items():
                if(paths[neighbour].distance > paths[currentVertex].distance + edgeCost):
                    paths[neighbour].distance = paths[currentVertex].distance + edgeCost
                    paths[neighbour].previous = currentVertex

                if neighbour in unvisited:
                    if(edgeCost <= nextVertexCost):
                        nextVertex = neighbour
                        nextVertexCost = edgeCost

            if(unvisited):
                unvisited.remove(currentVertex)
                currentVertex = nextVertex
        return paths

graph = Graph([
    ("a", "b", 7),  ("a", "c", 9),  ("a", "f", 14), ("b", "c", 10),
    ("b", "d", 15), ("c", "d", 11), ("c", "f", 2),  ("d", "e", 6),
    ("e", "f", 20)])



paths = graph.dijkstra("a", "e")
print(paths)
key = 'e'
result = ''
while key is not None:
    result = key + result
    key = paths[key].previous
print(result)
print("Cost: " + str(paths['e'].distance))