Algoritmo eficiente de asignación/corrección de etiquetas para el problema de caminos mínimos

  1. González Martín, Carlos
  2. Sedeño Noda, Antonio
Book:
XXX Congreso Nacional de Estadística e Investigación Operativa y de las IV Jornadas de Estadística Pública: actas

Publisher: Comité organizador del XXX Congreso Nacional de Estadística e Investigación Operativa y IV Jornadas de Estadística Pública

ISBN: 978-84-690-7249-3

Year of publication: 2007

Congress: Congreso Nacional de Estadística e Investigación Operativa (30. 2007. Valladolid)

Type: Conference paper

Abstract

Dise�namos un nuevo algoritmo de caminos m´ýnimos utilizando el concepto de etiqueta pseudo permanente. Esta noci´on permite dividir el conjunto de nodos en dos subconjuntos: los nodos con etiquetas pseudo permanentes y su complementario. Desde este punto de vista, este nuevo m´etodo puede ser considerado con un algoritmo de asignaci´on de etiquetas similar al algoritmo de Dijkstra. Por otro lado, en el algoritmo no se sabe que nodos de los pseudo permanentemente etiquetados est´an permanentemente etiquetados. As´ý, tambi ´en es considerado un algoritmo del tipo de correcci´on de etiquetas. Adem´as el algoritmo posee buenas caracter´ýsticas: (1) una complejidad O(nm); (2) te´oricamente, el n´umero de arcos observados por nuestro algoritmo es menor que el mismo n´umero para los algoritmos previamente propuestos; (3) incorpora dos nuevas reglas para detectar circuitos de longitud negativa; (4) es sencillo y f´acil de implementar (no requiere estructuras de datos complejas).