Puedes modificar cualquier gráfico para que Dijkstra encuentre la solución con el mínimo número de aristas así:
Multiplique cada peso de borde con un número , luego agregue al peso para penalizar cada borde adicional en la solución, es decir
Esto no funciona para todos los valores de ; necesita ser al menos para que esto funcione. Si no es este número mínimo, es posible que no elija la ruta más corta. ¿Cómo encuentro este valor mínimo ?
PD. Esto se hizo recreativamente, terminé con la tarea hace mucho tiempo.
algorithms
graph-theory
shortest-path
El gato no divertido
fuente
fuente
Respuestas:
Dado un gráficoG=(V,E,w) , definimos sol′= ( V, E,w′) con w′(e)=aw(e)+1 dónde a=|E|+ε para algunos ε≥0 como se propone en los comentarios de la pregunta.
El lema se sigue directamente de la definición dew′ .
Llama al resultado de Dijkstra enG′ P , que es el camino más corto en G′ . AsumirP no era un camino más corto con menos aristas (entre todos los caminos más cortos) en G . Esto puede suceder de dos maneras.
Entonces, hay un camino
Entonces, hay otro camino más corto
Como ambos casos han llevado a una contradicción,P es de hecho un camino más corto con menos aristas en G .
Eso cubre la mitad de la propuesta. Qué pasaa<|E| es decir a=|E|−ε con ε∈(0,|E|) ?
fuente