C'è un grafico non orientato in cui a ogni nodo viene assegnato un colore. Devo trovare il percorso più breve da qualsiasi nodo di colore blu a qualsiasi nodo di colore rosso. (Altri colori possono anche esistere nel grafico e anche se non importa ma non si sa quanti colori ci sono.) Come posso farlo in tempo polinomiale?Trovare il percorso più breve tra due nodi appartenenti a due sottoinsiemi disgiunti di un grafico
Come suggerimento, aggiungi due nuovi nodi al grafico: chiamali s e t. Collega s a ciascun nodo blu con un limite di costo 0 e ogni nodo rosso a t con un limite di costo 0. Quindi trova il percorso più breve da s a t.
Spero che questo aiuti!
grazie, questa è davvero la soluzione. – anirudh
Polinomiale per aggiungere i nodi s e t e per trovare il percorso più breve tra di essi (ad esempio con Dijkstra), così è polinomiale. – pvoosten
@lbp Ci sono molti modi semplici per risolverlo in tempo polinomiale, si potrebbe fare Floyd-Warshall e trovare la coppia (blu, rossa) con una distanza minima. Potresti fare Dijkstra | red | * | blu | tempi, molto inefficienza, e ancora essere polinomiale. Ma questa risposta fornisce un modo efficace, non solo polinomiale. – sdcvvc
Sono sicuro che l'algoritmo di Dijkstra può essere utilizzato in qualche modo per risolvere questo problema, ma non sono stato in grado di capire come. – anirudh