Resumen algoritmos grafos (Algoritmos III)

Dado un grafo $G(V,E)$, $n=|V|$ y $m=|E|$.

Árbol Generador Mínimo

Prim

• Técnica: Goloso
• Complejidad: $O(n^{2})$ ó $O(m\log n)$.
  • adjacency matrix, searching $O(n^{2})$
  • binary heap (as in pseudocode below) and adjacency list $O((n+m)\log n)=O(m\log n)$
  • Fibonacci heap and adjacency list $O(m+n\log n)$
• Invariante: Conecta iterativamente un conjunto de nodos conexo eligiendo siempre la arista de menor peso que no cierra un ciclo.

Kruskal

• Técnica: Goloso
• Complejidad: $O(m\log n)$
• Invariante: Selecciona el mínimo eje (siempre que no cierre un circuito) n-1 veces.

Camino mínimo desde un nodo $s$

Dijkstra

• Técnica: Goloso
• Complejidad: $O((n+m)\log n)$. $O(n\log n+m)$ con Fibonacci Heap.
• Invariante: Relaja(*) ejes iterativamente, tomando vértices en orden creciente de distancia a $s$.
• Consideraciones: No es correcto si existen aristas con peso negativo.

Bellman-Ford

• Complejidad: $O(nm)$
• Invariante: Para cada vértice, recorre sus aristas relajando(*) ejes. Caso general (con posibles ciclos de peso negativo).

Relax (*)

 for i from 1 to size(vertices)-1:
     for each edge uv in edges: // uv is the edge from u to v
         if u.distance + uv.weight < v.distance:
             v.distance := u.distance + uv.weight
             v.predecessor := u

Camino mínimo entre todo par de nodos

Dantzig

• Técnica: Dinámico.
• Complejidad: $O(n^{3})$
• Invariante: En cada paso $k$ considera el subgrafo inducido por los vértices $1,...,k$.

Floyd-Warshall

• Técnica: Dinámico
• Complejidad: $O(n^{3})$
• Invariante: Toma camino mínimo entre $i$ y $j$ pasando por $k$ nodos ($k\in [1..n]$).

      foreach $k\in [1..n]$: $d_{ij}\gets min(d_{ij},d_{ik}+d_{kj})$

Flujo máximo de $s$ a $t$

Edmonds-Karp

• Complejidad: $O(nm^{2})$