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

Carlos González Martín , Antonio Sedeño Noda

• 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).