Puede que me importe la cantidad mínima de saltos o el peso mínimo de las sumas de aristas que tengo que atravesar entre dos vértices

Web para visualizar: Create Graph online and find shortest path or use other algorithm

Grafo sin ciclos (árbol)

def DFS(origen, grafo):
	Pila = Pila()
	Padres = {}
	Pila.apilar((NULL, origen))
	while not pila.vacia():
		o,v = pila.desapilar()
		padre[v] = o
		for n in grafo.vecinos[v]:
			pila.apilar((v, n))
	return Padres

En el diccionario me queda:

{A: NULL, C:A, G:C, H:C, B:A, E:B, F:E}

Y después puedo usar este dicc para calcular el camino mínimo

Me guardo las distancias en el diccionario para guardar siempre el camino mínimo

def DFS(origen, grafo):
	Pila = Pila()
	Padres = {}
	distancias = {}
	Pila.apilar((NULL, origen, 0))
	while not pila.vacia():
		o,v, d = pila.desapilar()
		if not v in distancia or distancia[v] > d: #Si la distancia que estaba es más chica que la de ahora, me quedo con la más chica y no hago nada
			Padres[v] = o
			distancia[v] = d
		for n in grafo.vecinos[v]:
			pila.apilar((v, n, d+1))
	
	return Padres, distancias

Ejemplo con este grafo

Padres = { A: NULL, F:A, B:A, E:B}

Distancias = { A:0, F:1, B:1, E:2 }

y la cola que voy poniendo y sacando

Grafo con ciclos

Vamos a usar BFS porque si existe un camino con distancia uno lo voy a ver en la primera iteración

def BFS(origen, grafo):
	Cola = Cola()
	distancias = {}
	padres = {}
	visitados = set()
	cola.encolar((origen, 0))
	padres[origen] = NULL
	visitados.add(origen)
	
	while not cola.vacia():
		v, d = cola.desencolar()
		distancia[v] = d
		for n in grafo.vecinos[v]:
			if n not in visitados:
				cola.encolar((n, d+1))
				visitados.add(n)
				padres[n] = v
			
	return padres, distancias

Esto quedaría

padres = {A:NULL, C:A, B:A, D:C, E:C, G:C}

distancias = {A:0, C:1, B:1, D:2, E:2, G: 2, F:2}

visitados = {A, C, D, B, E, G, F}

Empezamos en A

(y vamos encolando)

Por la naturaleza de BFS (de hacerlo en width) siempre voy a agregar el camino mínimo → siempre que lo veo por primera vez ese es el camino mínimo

Orden

• Tiempo O(|V| + |E|)
• Memoria: O(b^d)

BFS bidireccional (optimización del caso de grafo con ciclos)

Hago una iteración de BFS desde un nodo y una desde el otro (de los que me quiero fijar el camino mínimo) → me sirve cuando quiero solo el camino entre dos cosas

• Orden en memoria → O(b^(d/2))