Sobre caminos mínimos en grafos con pesos negativos
No suelo traer aquí con tanta frecuencia otros temas relacionados con mi trabajo (en particular, con mis clases) pero me gusta anotar algunas cosas y en esta ocasión le ha tocado a Finally, a Fast Algorithm for Shortest Paths on Negative Graphs por varios motivos.
El problema de encontrar los caminos mínimos (de menor peso) en un grafo está resuelto hace mucho tiempo (año 1956 por Edsger Dijsktra) con una estrategia vorazsiempre que los pesos sean positivos. Sin embargo, la cosa se complica cuando permitimos que haya pesos negativos en el grafo. Tanto, que sigue siendo un problema a la espera de buenas soluciones.
La existencia de estas soluciones eficientes pueden hacernos pensar que ya no es interesante preocuparse de estos problemas. Sin embargo, de vez en cuando recibimos ‘buenas’ noticias, como en este caso: se ha publicado una solución Negative-Weight Single-Source Shortest Paths in Near-linear Time para el problema más general, que permite ejes de peso negativo.
Aunque dicen que es un algoritmo sencillo de explicar y de programar, conviene rdecir que hay que descomponer el grafo y utilizar técnicas de aleatorización.