Complementos I Práctica Lab 4

#! /usr/bin/python
# 4ta Practica Laboratorio
# Complementos Matematicos I
# Consigna: Implementar los siguientes metodos

from Queue import PriorityQueue

def dijkstra(grafo, vertice):
    '''
    Dado un grafo (en formato de listas con pesos), aplica el algoritmo de
    Dijkstra para hallar el COSTO del camino mas corto desde el vertice de origen
    al resto de los vertices.
    Formato resultado: {'a': 10, 'b': 5, 'c': 0}
    (Nodos que no son claves significa que no hay camino a ellos)
    '''
    diccionario = {}
    diccionario[vertice] = 0

    cola = PriorityQueue()
    cola.put((0,vertice))

    while not cola.empty():
        (peso_actual, vert_actual) = cola.get()
        if(diccionario[vert_actual] < peso_actual):
            continue
        for (origen, destino, peso) in grafo[1]:
            if(origen == vert_actual):
                if(not(diccionario.has_key(destino)) or peso_actual + peso < diccionario[destino]):
                    diccionario[destino] = peso_actual + peso
                    cola.put((peso_actual + peso, destino))

    return diccionario


def dijkstra_2(grafo, vertice):
    '''
    Dado un grafo (en formato de listas con pesos), aplica el algoritmo de
    Dijkstra para hallar el CAMINO mas corto desde el vertice de origen
    a cada uno del resto de los vertices.
    Formato resultado: {'a': ['a'], 'b': ['a', 'b'], 'c': ['a', 'c']}
    (Nodos que no son claves significa que no hay camino a ellos)
    '''
    diccionario = {}
    diccionario[vertice] = (0, [vertice])

    cola = PriorityQueue()
    cola.put((0,vertice))

    while not cola.empty():
        (peso_actual, vert_actual) = cola.get()
        if( diccionario[vert_actual][0] < peso_actual):
            continue
        for (origen, destino, peso) in grafo[1]:
            if(origen == vert_actual):
                if(not(diccionario.has_key(destino)) or peso_actual + peso < diccionario[destino][0]):
                    diccionario[destino] = (peso_actual + peso, diccionario[origen][1] + [destino])
                    cola.put((peso_actual + peso, destino))

    return {vertice:camino for vertice,(peso, camino) in diccionario.items()}


def main():
    pass

if __name__ == "__main__":
    main()