MAX_VAL=2**10
V=[]
E=[]
D=[]
P=[]
S=[]
VR=[]
DC=[0]
a = 0
n1= int(raw_input("ingrese el numero de vertices del grafo "))
for i in range (0,n1):
	vertice= str(raw_input('Nombre del vertice ' ))
	tupla = (vertice)
	V.append(tupla)
	D.append(MAX_VAL)
	P.append(' ')
print "Los vertices ingresados son:"
print V
n2= int(raw_input("ingrese el numero de arcos del grafo "))
for i in range (0,n2):
	inicial= str(raw_input('Nodo inicial: ' ))
	terminal=  str(raw_input('Nodo terminal: '))
	valor= int(raw_input('valor arista: '))
	tupla = (inicial,terminal,valor)
	E.append(tupla)	
print "El listado de aristas son: "
print E
def relajar(nodo):	
	peso = D[V.index(nodo)]
	for a in E[:]:
		if a[0] == nodo:
			print "Arco:"
			print a
			if a[1] not in S: 
				objetivo_indice = V.index(a[1])
				peso_actual = D[objetivo_indice]
				print objetivo_indice
				if peso_actual > peso + a[2]:
					D[objetivo_indice] = peso + a[2]
					P[objetivo_indice] = nodo 
					DC.append(D[objetivo_indice])
			E.remove(a)				
def extraer_barato():	
	print "Este es el costo minimo"
	print DC
	min_val = min(DC)
	DC.pop(DC.index(min_val))
	return D.index(min_val)	
def algo():
	while VR != []:
		nodo_a_considerar = V[extraer_barato()]
		print "Ahora el nodo a revisar es "+(nodo_a_considerar)
		VR.remove(nodo_a_considerar)
		S.append(nodo_a_considerar) 
		relajar(nodo_a_considerar)
	print "Este es el listado de valores de las rutas =",D
	print "P =",P
	

	
def init():
	VR[:]=V[:]
	DC[0] = D[0] = 0
def main():
	init()
	algo()

if __name__ == '__main__':
    main()