Supongamos que tengo un grafo dirigido con pesos de arista no negativos. Además, cada vértice es "verde" o "rojo". Supongamos que mis vértices de origen y destino son rojos.
Teniendo en cuenta todo esto, ¿cómo encuentro el camino más corto con un número impar de vértices verdes?
¿Qué te parece esto? En Algoritmo de Dijkstra en lugar de almacenar una distancia para cada vértice, almacena dos distancias que registren la distancia mínima al vértice a través de caminos con números pares e Impares de vértices verdes, respectivamente. Mantener un conjunto de distancias no visitadas (en lugar de vértices), y tratar cada distancia por separado a efectos de encontrar la distancia mínima en el conjunto no visitado, visitarla y marcarla como visitada. Terminar cuando la distancia al vértice de destino con un número impar de vértices verdes sea la distancia mínima en el conjunto no visitado.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
