"""Implementação em Python3 para o Algorítmo de Dijkstra"""

class Graph:
    """docstring for Graph"""
    def __init__(self):
        self.nodes = {}
        self.edges = {}

    def all_nodes(self):
        """ Retorna todos os nós """
        return self.nodes.values()

    def add_edge(self, node1, node2, cost):
        """ Adiciona uma aresta entre dois nós """
        self.edges[self.nodes[node1], self.nodes[node2]] = cost
        self.edges[self.nodes[node2], self.nodes[node1]] = cost

        self.nodes[node1].neighbors.append(self.nodes[node2])
        self.nodes[node2].neighbors.append(self.nodes[node1])

    def add_node(self, label):
        """ Cria um nó com a label passada """
        self.nodes[label] = Node(label)

    def distance_between(self, node1, node2):
        """ Retorna o custo da aresta entre dois nós """
        return self.edges[node1, node2]

class Node:
    """ Classe que representa um Nó """
    def __init__(self, label):
        self.label = label
        self.distance = 999
        self.previous = None
        self.neighbors = []

    def get_neighbors(self):
        """Retorna todos os vizinhos deste nó"""
        return self.neighbors


def dijkstra(graph, source):
    """Calcula o caminho mínimo utilizando o método de Dijkstra"""

    source.distance = 0

    all_nodes = graph.all_nodes()

    while all_nodes:
        # Ordena os nós por ordem CRESCENTE de distancia
        all_nodes = sorted(all_nodes, key=lambda x: x.distance)
        # Retira o nó com a menor distância
        min_node = all_nodes.pop(0)


        for neighbor in min_node.get_neighbors():
            # Soma entre caminho percorrido até aqui + o caminho até o vizinho
            alternative_path = min_node.distance + graph.distance_between(min_node, neighbor)

            # Se o caminho passando pelo vizinho é menos custoso que o caminho anterior
            # Relaxa o nó
            if alternative_path < neighbor.distance:
                neighbor.distance = alternative_path
                neighbor.previous = min_node

    return graph

def make_path(node):
    """Cria o caminho mínimo até o nó indicado"""
    path = []

    while node:
        path.insert(0, node.label)
        node = node.previous

    return path

def main():
    """ Main function """
    graph = Graph()
    graph.add_node(1)
    graph.add_node(2)
    graph.add_node(3)
    graph.add_node(4)
    graph.add_node(5)
    graph.add_node(6)

    graph.add_edge(1, 2, 2)
    graph.add_edge(1, 3, 4)
    graph.add_edge(2, 3, 1)
    graph.add_edge(2, 4, 4)
    graph.add_edge(2, 5, 2)
    graph.add_edge(3, 5, 3)
    graph.add_edge(4, 5, 3)
    graph.add_edge(4, 6, 2)
    graph.add_edge(5, 6, 2)

    dijkstra(graph, graph.nodes[1])

    for key, value in graph.nodes.items():
        print(key, value.distance)

    print(make_path(graph.nodes[6]))

if __name__ == '__main__':
    main()