Chemin avec le nombre minimum de modifications dans le graphique avec les couleurs

Question

J'ai un graphique orienté avec des bords colorés (rouge & bleu) qui peut contenir des cycles. La question est d'écrire un algorithme à deux sommets (s, t) qui trouve le chemin avec le nombre minimal de changements de couleur entre s et t (si un tel chemin existe).

J'ai trouvé une solution en utilisant une variante de Dijkstra (j'ai créé un nouveau graphique où chaque sommet correspond à un bord du graphique précédent, et contient la couleur du bord. une arête dans l'ancien graphe, alors (1/2) est un sommet dans le nouveau.J'ai connecté les sommets "bords adjacents", et les arêtes du nouveau graphe qui change de couleur ont un poids de 1, où la même transition de couleur est 0).

Je cherche une solution en temps linéaire (de V et E). Celui ci-dessus utilise des arêtes VxE dans le nouveau graphique.

Y a-t-il une telle solution pour trouver le chemin minimal?

Answer 1

Première phase: réduction au problème du chemin le plus court.

1. Pour chaque nœud i, nous créons deux noeuds i_red et i_blue.
2. Pour chaque bord bleu i->j, nous créons deux arêtes i_red->j_blue de poids 1 et i_blue->j_blue de poids 0.
3. Nous traitons les bords rouges de manière similaire.
4. Nous avons également besoin d'un noeud de démarrage qui est connecté avec start_red et start_blue avec un poids de connexion de 0.
5. Similaire au nœud cible, qui est connecté avec target_red et target_blue avec le poids 0 -connections.

Maintenant, recherchez le chemin le plus court entre le nœud de départ nouvellement créé et le nœud cible nouvellement créé. Il y a deux fois plus de nœuds et deux fois plus d'arêtes que dans le graphe d'origine, donc la réduction est linéaire.

Après avoir réduit le problème à la plus courte recherche de chemin, vous pouvez effectuer les opérations suivantes:

1. étape: utiliser uniquement les contours avec un poids 0, traiter le graphique comme un non orienté et avec l'aide de BFS vous pouvez trouver tous les composants dans ce graphique 0-edge en temps linéaire. Etape: exécutez bfs sur le graphe où les composants de l'étape précédente sont collés ensemble en tant que super-noeuds, donc tous les arêtes ont un poids 1 et bfs trouvera le chemin le plus court.

Il est évident que les trois parties de cet algorithme (BFS à 0-bord graphique, collage des éléments de super-noeuds et les bfs du graphique résultant) exécuter en temps linéaire.