Dijkstra favorecerá la solución con el menor número de bordes si varias rutas tienen el mismo peso

9

Puedes modificar cualquier gráfico G 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 decira1

w(u,v)=aw(u,v)+1

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 ?aaxax

PD. Esto se hizo recreativamente, terminé con la tarea hace mucho tiempo.

El gato no divertido
fuente
Si dos caminos tienen el mismo peso, se debe elegir el que tenga menos aristas. Lo siento. Veo que no lo dejé claro.
The Unfun Cat
1
También puedes hacerlo agregando ϵ a todos los pesos de borde, donde ϵ<m/e, m = peso mínimo del borde, e = número de bordes en la ruta más corta (o incluso en general, si no conoce la longitud más corta de la ruta) .
BlueRaja - Danny Pflughoeft
1
Dato interesante, gracias. Habrá que mirarlo.
The Unfun Cat

Respuestas:

5

Dado un gráfico G=(V,E,w), definimos G=(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.

Lemma
LetP un camino en G con costo Ces decir w(P)=C. Entonces,P ha costado aC+|P| en Ges decir w(P)=aC+|P|.

El lema se sigue directamente de la definición de w.

Llama al resultado de Dijkstra en G 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.

  1. P no es el camino más corto en G.
    Entonces, hay un caminoP con w(P)<w(P). Como|P|,|P||E|a, esto implica que también w(P)<w(P)con el lema anterior. Esto contradice queP fue elegido como el camino más corto en G.
  2. Pes una ruta más corta pero hay una ruta más corta con menos aristas.
    Entonces, hay otro camino más cortoP - es decir w(P)=w(P) -- con |P|<|P|. Esto implica quew(P)<w(P) por el lema anterior, que nuevamente contradice que P es un camino más corto en G.

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|)?


  1. En realidad, también necesitamos eso a o todos los pesos en Gson enteros De otra manera,w(P)<w(P) no causa los pesos en G ser al menos |E|aparte. Sin embargo, esto no es una restricción; siempre podemos escalarw con un factor constante para que todos los pesos sean enteros, suponiendo que comencemos con pesos racionales.
Rafael
fuente
Todavía no he podido encontrar una prueba de que a=|E| es la más pequeña apara lo cual esto funciona. Lo pensaré un poco más.
Raphael