Hay un gráfico no dirigido en el que a cada nodo se le asigna un color. Tengo que encontrar el camino más corto desde cualquier nodo de color azul a cualquier nodo de color rojo. (Otros colores también pueden existir en el gráfico y aunque no importa, pero no se sabe cuántos colores hay). ¿Cómo puedo hacerlo en tiempo polinomial?Encontrar la ruta más corta entre dos nodos pertenecientes a dos subconjuntos disjuntos de un gráfico
Como sugerencia, agregue dos nuevos nodos al gráfico; llámelos s y t. Conéctese a cada nodo azul con un borde de costo 0 y cada nodo rojo a t con un borde de costo 0. Luego, encuentre la ruta más corta desde s hasta t.
Espero que esto ayude!
gracias, esta es de hecho la solución. – anirudh
Polinomio tanto para agregar los nodos syt como para encontrar la ruta más corta entre ellos (por ejemplo, con Dijkstra), por lo que es polinomial. – pvoosten
@lbp Hay muchas maneras fáciles de resolverlo en tiempo polinomial, puedes hacer Floyd-Warshall y encontrar el par (azul, rojo) con una distancia mínima. Podrías hacer Dijkstra | red | * | azul | veces, muy ineficientemente, y aún ser polinomio. Pero esta respuesta da una manera eficiente, no solo polinomial. – sdcvvc
Estoy seguro de que el algoritmo de Dijkstra se puede usar de alguna forma para resolver esto, pero no he podido averiguar cómo. – anirudh