Modificado camino más corto utilizando el algoritmo de Bellman-Ford de Dijkstra o de

Question

¿Cómo podemos usar del algoritmo de Bellman-Ford Dijkstra o para encontrar la ruta más corta en un gráfico cuya algunos de los bordes se ven afectados si vamos vértices específicos. De tal manera que, la longitud del borde afectada será más que o menos que la longitud original.

Answer 1

Si entiendo este derecho, si desea cambiar el costo de una ventaja en un gráfico en función de los nodos que son visitados en su camino actual. Un ejemplo de los comentarios es:

"Edge AB tiene una longitud de 3, pero si también visitar el nodo C, la longitud de AB será 5"

Ahora bien, no parece ser una forma de que algo así como el algoritmo de Djikstra a ser utilizado, ya que es un paso en esa codiciosos algoritmo que recoge el nodo 'mejor' en cada etapa. La idea de que la 'mejor' nodo en ese punto puede cambiar en un momento posterior (debido a una norma como arriba) viola el concepto del enfoque codiciosos que supone que estamos visitando efectivamente nodos en orden de mejor a peor costo. No estoy seguro de si esto es NP duro como se sugiere, pero ciertamente no se puede usar un tipo Dijikstra de enfoque desde el principio. 1 para el problema sin embargo.