Orden del dijkstra

O(|E| <decreasekey> + |V| <remove min>)

Con heap O((|E| + |V|) log(|V|))

Con ABH: O((|E| + |V| log(|V|))

Bellman–ford Algorithm

Ejemplo

El camino a C se va achicando cada vez que paso por el ciclo, entonces cuál sería el camino mínimo?

def BF(origen, grafo):
	Para todo v en grafo-vertices:
		distancia[v] = infinito #distancia es un diccionario
	distancia[origen] = 0
	for i in range(|V|-1):
		for(u, v) in grafo.aristas:
			if distancia[v] > distancia[u] + peso(u, v):
				distancia[v] = distancia[u] + peso(u, v)
		for(u, v) in grafo.aristas:
			if distancia[v] > distancia[v] + peso(u, v):
				return NULL #detecta el ciclo con pesos negativos (solo lo detecta)
		return distancia

Máximo camino en un grafo de |V| vértices = |V| -1

Arranca todas las distancias en infinito menos la primera

Cuando encuentro el primero que cumple el if actualizo la distancia

Orden temporal: O(|V| |E|) con |E| ~ |V|

Peor caso: O(|V|^3)

Programación dinámica

• Greedy (golosa)
• Fuerza bruta
• Backtracking
• Programación dinámica

Fuerza bruta

Probar todo