Algoritmos de Grafos: Conceptos y Pseudocódigo

Este documento presenta una revisión de varios algoritmos fundamentales en la teoría de grafos, incluyendo Dijkstra, Floyd, Prim y Kruskal. Se proporciona pseudocódigo y una descripción de cada algoritmo.

Algoritmo Unir Particiones

Este algoritmo se utiliza para unir particiones en un grafo, dado un diccionario que mapea vértices a números de partición y una arista que especifica las particiones a unir.

Entrada:

• DIC: Diccionario con vértice como clave y número de partición como valor.
• arista: Arista con origen y destino que indican las particiones a unir.

Salida:

• DIC: Diccionario actualizado.

Pseudocódigo:

MIN <- ∞
Para cada vértice en DIC:
  Si DIC[vértice] = DIC[arista.origen] o DIC[vértice] = DIC[arista.destino]:
    DIC[vértice] <- MIN
  Fin Si
Fin Para
Devolver DIC

Algoritmo de Floyd

El algoritmo de Floyd encuentra los caminos más cortos entre todos los pares de vértices en un grafo ponderado. Opera construyendo una serie de matrices que representan las distancias mínimas entre vértices, considerando vértices intermedios.

Se parte de una matriz M0 donde se tiene la mejor forma de llegar de cada vértice a todos los demás sin pasar por ningún vértice intermedio, e iremos encontrando las matrices intermedias M1, M2, …, hasta llegar a Mn, donde n es la cantidad de vértices del grafo.

Algoritmo de Dijkstra

El algoritmo de Dijkstra encuentra el camino más corto desde un vértice origen a todos los demás vértices en un grafo ponderado con aristas no negativas.

Entrada:

• G(V, A): Grafo con vértices V y aristas A.
• origen: Vértice origen.

Salida:

• Diccionario que devuelve el costo mínimo para llegar a cada vértice.

Pseudocódigo (con verificación de conexidad):

dic <- Diccionario()
Para cada v en G.vértices:
  Dic[v] <- ∞
Fin Para
dic[origen] <- 0
visitados <- {}
mientras #visitados < #G.vértices:
  min <- ∞
  vértice <- null
  Para cada val en DIC:
    Si DIC[val] < min y val no está en visitados:
      min <- DIC[val]
      vértice <- val
    Fin Si
  Fin Para
  visitados.agregar(vértice)
  Para cada a en G.aristas:
    Si a.origen = vértice:
      Si dic[vértice] + a.peso < dic[a.destino]:
        dic[a.destino] <- dic[vértice] + a.peso
      Fin Si
    Fin Si
  Fin Para
Fin Mientras
Devolver DIC

Pseudocódigo de Dijkstra (origen y destino dados):

dic <- Diccionario()
dicaux<-Diccionario()
Para cada v en G.vértices:
  Dic[v] <- ∞
Fin Para
dic[origen] <- 0
visitados <- {}
mientras #visitados < #G.vértices:
  min <- ∞
  vértice <- null
  Para cada val en DIC:
    Si DIC[val] < min y val no está en visitados:
      min <- DIC[val]
      vértice <- val
    Fin Si
  Fin Para
  visitados.agregar(vértice)
  Para cada a en G.aristas:
    Si a.origen = vértice:
      Si dic[vértice] + a.peso < dic[a.destino]:
        dicaux[a.destino] <-  dic[vértice] + a.peso
        dic[a.destino] <- dic[vértice] + a.peso
      Si no:
          dic[a.destino] <- dic[vértice] + a.peso
      Fin Si
    Fin Si
  Fin Para
Fin Mientras
Devolver DICaux

Algoritmo de Prim

El algoritmo de Prim encuentra un árbol de expansión mínima (MST) para un grafo ponderado, conexo y no dirigido. El MST es un subgrafo que conecta todos los vértices con el menor peso total de aristas posible.

Entrada:

• G(V, A): Grafo con vértices V y aristas A.

Salida:

• Grafo que representa el árbol de expansión mínima.

Pseudocódigo (con verificación de conexidad):

Gaux <- (G.V, [])
F <- {un vértice arbitrario de G.V}
PI <- G.V - F
min <- ∞
Mientras #PI > 0:
  Para cada origen en F:
    Para cada destino en PI:
      Para cada arista en G.A:
        Si arista.origen = origen y arista.destino = destino:
          Si arista.peso < min:
            min <- arista
          Fin Si
        Fin Si
      Fin Para
    Fin Para
  Fin Para
  F <- F ∪ {min.destino}
  Gaux.aristas <- Gaux.aristas ∪ {min}
  PI <- PI - {min.destino}
Fin Mientras
Devolver Gaux

Algoritmo de Dijkstra (Devuelve Grafo)

Una variante del algoritmo de Dijkstra que devuelve el grafo solución y un grafo con los caminos mínimos.

Entrada: G: grafo de origen, v: nodo origen

Salida: A: grafo solución, R: grafo con los caminos mínimos

// Paso 1: Conjunto de vértices ya visitados
Visitados <- {}

// Paso 2: Grafo auxiliar
inicializar(A)
inicializar(R)
Para cada w de Vértices(G):
  agregarVértice(A, w)
  agregarVértice(R, w)
Fin Para

Para cada v0 adyacente a v:
  agregarArista(A, v, v0, Peso(G, v, v0))
  agregarArista(R, v, v0, Peso(G, v, v0))
Fin Para

// Conjunto de vértices pendientes de cálculo
Pendientes <- Vértices(G) \ {v}

// Paso 3
Mientras Pendientes ≠ {}:
  PesoArista(A, v, n) = min{PesoArista(A, v, p) | p ∈ Pendientes}
  Visitados <- Visitados ∪ {n}
  Pendientes <- Pendientes \ {n}
  auxPendientes <- Pendientes
  Mientras auxPendientes ≠ {}:
      p <- elegir(auxPendientes)
      auxPendientes <- auxPendientes \ {p}
      Si existeArista(A, v, w) Y existeArista(G, w, p):
          Si existeArista(A, v, p):
              Si PesoArista(A, v, w) + PesoArista(G, w, p) < PesoArista(A, v, p):
                  agregarArista(A, v, p, PesoArista(A, v, w) + PesoArista(G, w, p))
                  Para cada x en Vértices(R):
                      eliminarArista(R, x, p)
                  Fin Para
                  agregarArista(R, w, p, PesoArista(G, w, p))
              Fin Si
          Si no:
              agregarArista(A, v, p, PesoArista(A, v, w) + PesoArista(G, w, p))
              agregarArista(R, w, p, PesoArista(G, w, p))
          Fin Si
      Fin Si
  Fin Mientras
Fin Mientras
Devolver A

Algoritmo de Kruskal

El algoritmo de Kruskal también encuentra un árbol de expansión mínima (MST) para un grafo ponderado, conexo y no dirigido. A diferencia de Prim, Kruskal construye el MST agregando aristas en orden de peso creciente, siempre y cuando no formen un ciclo.

Entrada: Un grafo ponderado y conexo G(V,E)

Salida: Un árbol de expansión mínima T de G.

Pseudocódigo:

T <- Grafo vacío con los mismos vértices que G.
E' <-  Conjunto de aristas de G ordenadas por peso de menor a mayor.
Para cada arista (u,v) en E':
    Si u y v no están en la misma componente conexa de T:
        Agregar la arista (u,v) a T.
        Unir las componentes conexas de u y v en T.
    Fin Si
Fin Para
Devolver T

Algoritmo de Floyd (Detallado)

Una versión más detallada del algoritmo de Floyd.

Algoritmo Floyd
Entrada: G grafo de entrada
Salida: R: grafo con una arista con la distancia mínima entre cada par de vértices
inicializarGrafo(R)
copiarGrafo(G, R)
VérticesK = Vértices(G)
Para cada k en VérticesK:
    VérticesI = Vértices(G)
    Para cada i en VérticesI:
        VérticesJ = Vértices(G)
        Para cada j en VérticesJ:
            Si i ≠ j Y existeArista(R, i, k) Y existeArista(R, k, j):
                Si existeArista(R, i, j):
                    Si PesoArista(R, i, k) + PesoArista(R, k, j) < PesoArista(R, i, j):
                        agregarArista(R, i, j, PesoArista(R, i, k) + PesoArista(R, k, j))
                    Fin Si
                Si no:
                    agregarArista(R, i, j, PesoArista(R, i, k) + PesoArista(R, k, j))
                Fin Si
            Fin Si
        Fin Para
    Fin Para
Fin Para
Devolver R

Tablas (Ejemplos de Problemas y Algoritmos)

Las siguientes tablas muestran ejemplos de problemas y los algoritmos que se pueden utilizar para resolverlos:

Tabla 1: Problemas

1. Mochila y Archivos
2. Cambio y ANA
3. Cómic y PDF
4. Cultivos y Calorías
5. Agua

Tabla 2: Problemas y Algoritmos

1. Partición Mitad, Cambio
2. Ruta Aérea con Menos Escalas
3. Mochila
4. Procesadores con Tareas (Suma de Tareas)
5. Hamiltonianos

Tabla 3: Algoritmos

1. Quicksort
2. Merge y MergeSort
3. Kruskal (con peso acumulado y verificación de conexidad)
4. Unir Partición (Kruskal y teoría de Floyd)
5. Dijkstra (con verificación de conexidad)
6. Dijkstra (origen y destino dados)
7. Prim (con peso acumulado y verificación de conexidad)
8. Dijkstra (devuelve grafo)
9. Dijkstra (devuelve grafo, con teoría de Kruskal)
10. Floyd (algoritmo)