Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- """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()
Add Comment
Please, Sign In to add comment