author = 'Eden Thiago Ferreira'
import time
from pqdict import *
from grafos import *

class Dijkstra:
        
    def __init__(self, grafo=Digrafo()):
        self.grafo = grafo
        self.pt_a = None
        self.pt_b = None
        self.anterior = {}
        self.dist_total = 0
        self.visitados = set()
        self.nao_visitados = PQDict()
        self.__caminho = []
    
    def processar_ponto(self, pt_atual, dist_atual):
        for pt in self.grafo.arcos[pt_atual]:
            if pt not in self.visitados and (pt not in self.nao_visitados or self.nao_visitados[pt] > dist_atual + self.grafo.arcos[pt_atual][pt]):
                self.nao_visitados[pt] = dist_atual + self.grafo.arcos[pt_atual][pt]
                self.anterior[pt] = pt_atual
    
    def executar(self, pt_a, pt_b):
        self.pt_a = pt_a
        self.pt_b = pt_b
        self.nao_visitados[pt_a] = 0
        
        while self.nao_visitados:
            pt_atual, dist_atual = self.nao_visitados.popitem()
            self.processar_ponto(pt_atual, dist_atual)            
            self.visitados.add(pt_atual)
            self.dist_total = dist_atual
            if pt_atual == pt_b:
                break
    
    @property
    def caminho(self):
        if not self.__caminho:
            self.__caminho = _caminho(self.anterior, self.pt_a, self.pt_b)
        return self.__caminho
        
class AStar:

    def __init__(self, grafo=Digrafo()):
        self.grafo = grafo
        self.pt_a = None
        self.pt_b = None
        self.anterior = {}
        self.dist_total = 0
        self.visitados = set()
        self.nao_visitados = PQDict()
        self.distancia = {}
        self.__caminho = []
    
    def heuristica(self,pt):
        #return 0
        return self.grafo.dist(pt, self.pt_b)
    
    def processar_ponto(self, pt_atual, dist_atual):
        for pt in self.grafo.arcos[pt_atual]:
            if pt not in self.visitados and (pt not in self.distancia or self.distancia[pt] > dist_atual + self.grafo.arcos[pt_atual][pt]):
                self.distancia[pt] = dist_atual + self.grafo.arcos[pt_atual][pt]
                self.nao_visitados[pt] = dist_atual + self.grafo.arcos[pt_atual][pt] + self.heuristica(pt)
                self.anterior[pt] = pt_atual
    
    def executar(self, pt_a, pt_b):
        self.pt_a = pt_a
        self.pt_b = pt_b
        self.nao_visitados[pt_a] = 0 + self.heuristica(pt_a)
        self.distancia[pt_a] = 0
        
        while self.nao_visitados:
            pt_atual = self.nao_visitados.popitem()[0]
            dist_atual = self.distancia[pt_atual]
            self.processar_ponto(pt_atual, dist_atual)           
            self.visitados.add(pt_atual)
            self.dist_total = dist_atual
            if pt_atual == pt_b:
                break
    
    @property
    def caminho(self):
        if not self.__caminho:
            self.__caminho = _caminho(self.anterior, self.pt_a, self.pt_b)
        return self.__caminho
                
                
def _caminho(anterior, pt_a, pt_b):
    caminho = list()
    pt_atual = pt_b
    while pt_atual != pt_a:
        caminho.append(pt_atual)
        if pt_atual == 0:
            print('erroa: ',anterior,'\nerroc: ',caminho)
        pt_atual = anterior[pt_atual]
        
    caminho.append(pt_atual)
    caminho.reverse()
    return caminho
        

@@ -339,32 +339,60 @@
 ados = PQDict()%0A
+        self.num_passos = 0%0A
         self.__c
@@ -395,32 +395,32 @@
 .__caminho = %5B%5D%0A
-
     %0A    def pro
@@ -948,32 +948,65 @@
 .nao_visitados:%0A
+            self.num_passos += 1%0A
             pt_a
@@ -1724,24 +1724,52 @@
 tancia = %7B%7D%0A
+        self.num_passos = 0%0A
         self
@@ -2351,32 +2351,167 @@
 %5Bpt%5D = pt_atual%0A
+                if pt_atual == 0:%0A                    print('processar', self.distancia%5Bpt%5D, self.nao_visitados%5Bpt%5D,self.anterior%5Bpt%5D)%0A
     %0A    def exe
@@ -2714,32 +2714,65 @@
 .nao_visitados:%0A
+            self.num_passos += 1%0A
             pt_a
@@ -2810,16 +2810,16 @@
 em()%5B0%5D%0A
-
         
@@ -2852,32 +2852,118 @@
 ancia%5Bpt_atual%5D%0A
+            if pt_atual == 0:%0A                print('executar', pt_atual, dist_atual)%0A
             self

Update caminhos_minimos.py 30/05/2014