Grafos y Diksra

import numpy as np

class Grafo:

#generador de grafo con 'cant_nodos' nodos

def __init__(self, cant_nodos):

self.matriz_ad = np.zeros((cant_nodos, cant_nodos))

self.cant_nodos = cant_nodos

#agrega 'cant_nodos_nuevos' nodos al grafo

def agregar_nodos(self, cant_nodos_nuevos):

#cambio el tamaño de la matriz sumandole cant_nodos_nuevos

self.cant_nodos += cant_nodos_nuevos

#agregar 'cant_nodos_nuevos' filas y columnas

for i in range(cant_nodos_nuevos):

self.matriz_ad = np.pad(self.matriz_ad, ((0, 1), (0, 1)), mode='constant')

#crea una arista dirccionada dede v a u, v y u indices del nodo

def agregar_arista(self, v, u, peso):

#valido que los nodos existan

if 0 <= u < self.cant_nodos and 0 <= v < self.cant_nodos:

#cargo el pedo de la arista en el lugar correspondiente de la matriz

self.matriz_ad[v][u] = peso

else:

print('Los modos ingresados no existen')

#imprime los valores actuales de la matriz de adyacencia

def mostrar_matriz(self):

for row in self.matriz_ad:

print(f"[ {', '.join(str(int(x)) for x in row)} ]")

print()

#funcion que devuelve y calcula el peso del el camino mas corto desde el 'nodo_inicio' a todos los nodos del grafo

def dijkstra(self, nodo_inicio):

if (0 <= nodo_inicio < self.cant_nodos):

#la funcion 'obtener_caminos' recorre el array precesores para reconstruir el camino mas corto desde el 'nodo_inicio' al 'nodo_fin'

def obtener_camino(precesores, nodo_inicio, nodo_fin):

camino = []

actual = nodo_fin

#mientras en el array de precesores no aparezca None (lo que significa que no he ya llegado al final del camino), sigo iterando

while actual is not None:

#inserto en la posicion 0 el valor

camino.insert(0, actual)

#para el nuevo valor es el precesos del valor actual

actual = precesores[actual]

#valido que si es nuvo valor es el 'nodo_inicio', si es asi lo agrego y paro el while

if actual == nodo_inicio:

camino.insert(0, nodo_inicio)

break

#retorno la lista separada por flechas para mostrar

return '->'.join(str(x) for x in camino)

distancias = [float('inf')] * self.cant_nodos

precesores = [None] * self.cant_nodos

distancias[nodo_inicio] = 0

visitado = [False] * self.cant_nodos

for _ in range(self.cant_nodos):

distancia_minima = float('inf')

#en u se va a guardar el nodo con la menor distancia en el array de distancias y que no ha sido visitado

u = None

for i in range(self.cant_nodos):

if not visitado[i] and distancias[i] < distancia_minima:

distancia_minima = distancias[i]

u = i

#si no hay nodos por visitar termino el for

if u is None:

break

#actualizo visitado para u

visitado[u] = True

#recorro la matriz para encontrar los adyacentes de u

for v in range(self.cant_nodos):

#chequeo que sea adyasente y que no se haya visitado ya

if self.matriz_ad[u][v] != 0 and not visitado[v]:

#calculo la distancia del vertice inicio al vertive v

alt = distancias[u] + self.matriz_ad[u][v]

#si la nueva distancia calculada es menor a la ya guardada actualizo la distancia y el precesor sino no hago nada

if alt < distancias[v]:

distancias[v] = alt

precesores[v] = u

#itero sobre las distancias e imprimo, para cada par de nodos calculo el camino y muestro la distancia

for i, d in enumerate(distancias):

print(f"camino de {nodo_inicio} a {i} es: {obtener_camino(precesores, nodo_inicio, i)} distancia: {d}")

else:

print('El nodo ingresado no existe')

g = Grafo(2)

g.agregar_nodos(3)

g.agregar_arista(0,2,1)

g.agregar_arista(0,3,2)

g.agregar_arista(1,0,1)

g.agregar_arista(2,1,1)

g.agregar_arista(2,3,3)

g.agregar_arista(4,0,5)

g.mostrar_matriz()

g.dijkstra(4)