Contexto histórico e ideas generales sobre caminos mínimos en grafos

El problema de camino mínimo en grafos, nace al intentar ir de un punto a otro minimizando el coste, este último representa la distancia  recorrida, tiempo empleado, costos, entre otros factores. Siendo los grafos la representación más usual de este tipo de problemas.

Nuestro problema puede estar definido para grafos dirigidos, no dirigidos o mixtos. 

Diremos que dos nodos son adyacentes si poseen una arista en común. Y en el caso de que el grafo sea dirigido, tendría que poseer una apropiada arista dirigida.

Llamamos camino en un grafo a una secuencia de vértices adyacentes.

Hay varios tipos de problemas de camino mínimo en grafos, entre ellos:

  • El problema de camino mínimo desde un origen.
  • El problema de camino mínimo con un destino.
  • El problema de camino mínimo entre todos los pares de vértices.
Es decir, nuestro problema va a consistir en encontrar un camino entre dos o más nodos, tal que el peso de las aristas que lo constituyen sea mínimo. 


A continuación, vamos a ver la historia de algunos algoritmos más importantes relacionados con caminos mínimos en grafos:

  • Algoritmo de Dijkstra: Edsger Dijkstra describió este algoritmo de caminos mínimos en grafos, en 1959. Es uno de los algoritmos más conocidos en la teoría de grafos. La idea básica de este algoritmo consiste en, partiendo de un grafo conexo y de distancias no negativas, encontrar el camino de peso mínimo, entre el nodo origen y el resto de nodos del grafo. El algoritmo finaliza cuando se obtiene el camino mínimo entre el nodo origen hasta recorrer todos los nodos. Realizándose un total de \(n^2\) operaciones, siendo \(n\) el número de nodos. Este algoritmo además trabaja solo con pesos positivos de las aristas. Tiene diversas aplicaciones, como su  uso en el protocolo de enrutamiento Open Shortest Path First (OSPF) o en (BFS) Breadth-First Search. Además de su vital importancia en el campo de la telemática, ya que este tipo de problemas, tiene un número de nodos muy alto.                                                                                                                              

  •  Algoritmo de Bellman-Ford: Fue desarrollado por Richard Bellman, Samuel End y Lester Ford. Este algoritmo trata de encontrar el camino mínimo en un grafo dirigido, de forma similar a Dijkstra, pero a diferencia lo que hace es relajar todas las aristas y lo hace \(|V| -1\) veces, (siendo \(|V|\) el número de vértices en el grafo). De tal forma que esto le permite pasar por todos los nodos una vez. A diferencia del algoritmo de Dijkstra, que solo trabaja con pesos positivos, y toma directamente la arista con el peso más pequeño, este algoritmo trabaja también con aristas con peso negativo. El problema de trabajar con aristas negativas es que si nuestro camino contiene un ciclo de peso total negativo, entonces este problema no tendrá solución. Además  este método de resolución es más lento que el algoritmo de Dijkstra, debido a que el número de operaciones es mayor. Este tipo de algoritmo se usa en protocolos de encaminamientos basados en vector de distancias, por ejemplo el Protocolo de encaminamiento de información (RIP). También debemos destacar la mejora de este algoritmo en 1970. Yen describió una mejora del algoritmo de Bellman-Ford para grafos sin ciclos con peso negativo.                                                                                                                                            
  • Algoritmo de Floyd-Warshall: Este algoritmo de camino mínimo, trabaja con grafos dirigidos ponderados. Encuentra el camino entre todos los pares de vértices, en una sola ejecución, lo que agiliza el proceso. Bernard Roy en 1959, fue el primero en describir este algoritmo. Pero podemos encontrar diversos pseudónimos, debido a que su variación más conocida que fue en 1962 por Robert Floyd, la cuál se basó en un teorema de Stephen Wharshall. Este último, en 1962 de forma totalmente independiente también dedujo este algoritmo. Entre los nombres con los que conocemos este algoritmo cabe destacar: Algoritmo de Floyd, Algoritmo de Roy-Floyd, Algoritmo de Roy-Wharshall, entre otros. Siendo un gran ejemplo de la programación dinámica, esto quiere decir, que es muy veloz, ya que resuelve el algoritmo a través de subproblemas superpuestos y subestructuras óptimas. La programación dinámica fue inventada por Richard Bellman en 1953. 

Last modified: Thursday, 21 June 2018, 11:58 PM