daily pastebin goal
47%
SHARE
TWEET

Untitled

a guest May 17th, 2018 105 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. """Implementação em Python3 para o Algorítmo de Dijkstra"""
  2.  
  3. class Graph:
  4.     """docstring for Graph"""
  5.     def __init__(self):
  6.         self.nodes = {}
  7.         self.edges = {}
  8.  
  9.     def all_nodes(self):
  10.         """ Retorna todos os nós """
  11.         return self.nodes.values()
  12.  
  13.     def add_edge(self, node1, node2, cost):
  14.         """ Adiciona uma aresta entre dois nós """
  15.         self.edges[self.nodes[node1], self.nodes[node2]] = cost
  16.         self.edges[self.nodes[node2], self.nodes[node1]] = cost
  17.  
  18.         self.nodes[node1].neighbors.append(self.nodes[node2])
  19.         self.nodes[node2].neighbors.append(self.nodes[node1])
  20.  
  21.     def add_node(self, label):
  22.         """ Cria um nó com a label passada """
  23.         self.nodes[label] = Node(label)
  24.  
  25.     def distance_between(self, node1, node2):
  26.         """ Retorna o custo da aresta entre dois nós """
  27.         return self.edges[node1, node2]
  28.  
  29. class Node:
  30.     """ Classe que representa um Nó """
  31.     def __init__(self, label):
  32.         self.label = label
  33.         self.distance = 999
  34.         self.previous = None
  35.         self.neighbors = []
  36.  
  37.     def get_neighbors(self):
  38.         """Retorna todos os vizinhos deste nó"""
  39.         return self.neighbors
  40.  
  41.  
  42. def dijkstra(graph, source):
  43.     """Calcula o caminho mínimo utilizando o método de Dijkstra"""
  44.  
  45.     source.distance = 0
  46.  
  47.     all_nodes = graph.all_nodes()
  48.  
  49.     while all_nodes:
  50.         # Ordena os nós por ordem CRESCENTE de distancia
  51.         all_nodes = sorted(all_nodes, key=lambda x: x.distance)
  52.         # Retira o nó com a menor distância
  53.         min_node = all_nodes.pop(0)
  54.  
  55.  
  56.         for neighbor in min_node.get_neighbors():
  57.             # Soma entre caminho percorrido até aqui + o caminho até o vizinho
  58.             alternative_path = min_node.distance + graph.distance_between(min_node, neighbor)
  59.  
  60.             # Se o caminho passando pelo vizinho é menos custoso que o caminho anterior
  61.             # Relaxa o nó
  62.             if alternative_path < neighbor.distance:
  63.                 neighbor.distance = alternative_path
  64.                 neighbor.previous = min_node
  65.  
  66.     return graph
  67.  
  68. def make_path(node):
  69.     """Cria o caminho mínimo até o nó indicado"""
  70.     path = []
  71.  
  72.     while node:
  73.         path.insert(0, node.label)
  74.         node = node.previous
  75.  
  76.     return path
  77.  
  78. def main():
  79.     """ Main function """
  80.     graph = Graph()
  81.     graph.add_node(1)
  82.     graph.add_node(2)
  83.     graph.add_node(3)
  84.     graph.add_node(4)
  85.     graph.add_node(5)
  86.     graph.add_node(6)
  87.  
  88.     graph.add_edge(1, 2, 2)
  89.     graph.add_edge(1, 3, 4)
  90.     graph.add_edge(2, 3, 1)
  91.     graph.add_edge(2, 4, 4)
  92.     graph.add_edge(2, 5, 2)
  93.     graph.add_edge(3, 5, 3)
  94.     graph.add_edge(4, 5, 3)
  95.     graph.add_edge(4, 6, 2)
  96.     graph.add_edge(5, 6, 2)
  97.  
  98.     dijkstra(graph, graph.nodes[1])
  99.  
  100.     for key, value in graph.nodes.items():
  101.         print(key, value.distance)
  102.  
  103.     print(make_path(graph.nodes[6]))
  104.  
  105. if __name__ == '__main__':
  106.     main()
RAW Paste Data
Top