Resumen algoritmos grafos (Algoritmos III)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

Dado un grafo , y .


Árbol Generador Mínimo[editar]

Prim[editar]

  • Técnica: Goloso
  • Complejidad: ó .
    • adjacency matrix, searching
    • binary heap (as in pseudocode below) and adjacency list
    • Fibonacci heap and adjacency list
  • Invariante: Conecta iterativamente un conjunto de nodos conexo eligiendo siempre la arista de menor peso que no cierra un ciclo.

Kruskal[editar]

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


Camino mínimo desde un nodo [editar]

Dijkstra[editar]

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

Bellman-Ford[editar]

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

Relax (*)[editar]

 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[editar]

Dantzig[editar]

  • Técnica: Dinámico.
  • Complejidad:
  • Invariante: En cada paso considera el subgrafo inducido por los vértices .

Floyd-Warshall[editar]

  • Técnica: Dinámico
  • Complejidad:
  • Invariante: Toma camino mínimo entre y pasando por nodos ().
      foreach : 


Flujo máximo de a [editar]

Ford-Fulkerson[editar]

Edmonds-Karp[editar]

  • Complejidad: