16 Árboles generadores y caminos mínimos

dado un grafo $G$ (o un digrafo $\bar G$) ponderado

preguntas interesantes:

• ¿Cuál es un bosque generador con peso mínimo en $G$?
• dado un vertice $s\in \bar G$, ¿ Cuáles son los caminos mínimos hacia los demás vértices?
• ¿Cuáles con los caminos mínimos entre todas las parejas de vértices?

Hacia cada vértice $u\in G$ existe un camino desde $s$ con distancia mínima.

Las distancias a todos los vértices en uno de estos caminos a su vez son caminos mínimos.

Si $G$ es conexo, se puede construir un árbol con raíz $s\in G$ que determina todos los caminos mínimos hacia todos los vértices de $G$.

¿Algoritmo que calcule un bosque mínimo de un grafo $G$?

Algoritmo de KRUSKAL, complejidad $O(m \log n)$

Algoritmo de PRIM, complejidad $O(m \log n)$

¿Algoritmo que calcule un árbol mínimo desde un vértice $s$ en $\bar G$?

Algoritmo de DIJKSTRA, complejidad $O(n^2)$

El algoritmo funciona igual con grafos como con digrafos.

¿Se puede permitir pesos negativos?

pueden existir ciclos negativos, es decir, ciclos con pesos negativos

¿Algoritmo que calcule un árbol mínimo desde un vértice $s$ en $G$ si $G$ contiene pesos negativos?

Algoritmo de BELLMANN-FORD, complejidad $O(mn)$

El Algoritmo detecta la existencia de ciclos negativos en que caso termina sin solución.

¿Algoritmo que calcule los caminos mínimos entre todas las parejas de vértices incluyendo el caso de pesos negativos?

Algoritmo de FLOYD-WARSHALL, complejidad $O(n^3)$

El algoritmo detecta la existencia de ciclos negativos en que caso termina sin solución.

Mejoras:

si se tiene más información sobre los grafos y sus pesos se puede mejorar los algoritmos:

• si los pesos están confinados por una constante $W$:
• si el número de aristas $m$ está confinado por $O(n \log n)$: