Pregunta de teoría de grafos, Java. Qué algoritmo para lograr lo siguiente

Question

Tengo un gráfico, con nodos X y bordes Y. Bordes ponderados. El punto es comenzar en un nodo y detenerse en otro. Ahora aquí viene el problema;

Visualiza el problema. Los bordes son carreteras, y los pesos de los bordes son los límites máximos de peso para vehículos que circulan por las carreteras. Nos gustaría conducir el camión más grande posible de A a B. Por lo tanto, el peso máximo permitido para un camión que toma una ruta dada es el peso más pequeño de todos los bordes en esa ruta. Quiero el mayor peso máximo permitido para todas las rutas de A a B.

¿Puedo usar algún tipo de algoritmo de Dijkstra para este problema? No estoy seguro de cómo expresar este problema en forma de un algoritmo que pueda implementar. Cualquier ayuda es muy apreciada.

Actualización: Probé algunas cosas que no me funcionaron. Un nodo debería tener un camión máximo por cada borde entrante.

Answer 1

El algoritmo de Dijkstra debería funcionar, pero su " distance " En este caso es un poco raro. Tu & Quot; distancia & Quot; es el camión de tamaño máximo que puede llegar a un nodo. Llamemos a eso M [v] para un nodo v. Debe procesar los nodos en orden desde M [v] más grande hasta M [v] más pequeño (opuesto a Dijkstra normal), y calcular para cada borde e de v a w:

M[w] = max(M[w], min(e.weight, M[v]))

Answer 2

Esto suena (casi) exactamente como el problema de flujo máximo que se puede resolver de manera eficiente utilizando el algoritmo Ford-Fulkerson .

Como Keith ha señalado en un comentario, el algoritmo máximo debe variarse ligeramente para encontrar una ruta con un segmento de ruta mínimo maximizado, ya que el camión no puede & # 8217; t be dividido en varias partes.

Answer 3

Creo que estás buscando esto

Ruta más corta

editar: en realidad no, no estás, y el enlace de flujo máximo es correcto

Answer 4

Entonces, si entiendo esto correctamente, me preguntas " ¿Cuál es el camión más grande que puede conducir de A a B "

Para aplicar el algoritmo de Dijkstra, necesitará una forma de modelar " cost " ;. Si desea utilizar una implementación estándar, puede asignar la inversa del peso al costo. Por lo tanto, el borde de mayor costo es el que tiene el peso máximo más bajo. Por supuesto, dado que probablemente quiera usar enteros agradables, simplemente puede modificar las comparaciones en lugar de usar los inversos.

Answer 5

Está buscando optimizar una [ http://en.wikipedia.org/wiki/Flow_network ] . La capacidad es el límite de peso máximo de la carretera; y el flujo es el peso del camión.

Answer 6

Podría adoptar una especie de enfoque de árbol de expansión mínimo. Conecte los nodos un borde a la vez, primero los bordes de flujo más alto, hasta que A y B estén conectados. El último borde que agregó al gráfico es el borde de flujo más bajo que tendrá que cruzar para pasar de A a B. Probablemente no sea la solución más eficiente (O (N ² ) peor de los casos) , pero al menos es sencillo.

Answer 7

Este no es un problema de ruta más corta ni un problema de flujo máximo. En realidad no hay problema. Dijo: desea el peso máximo para todas las rutas A a B. Así que ve a generar todas las rutas desde A por BFS. Para todas las rutas que terminan en B, obtenga el peso mínimo de los bordes de la ruta.

Answer 8

Utilice algoritmo de Dijkstra con el inverso del peso máximo del camión como costo de borde, y el máximo de pesos de borde individuales como costo total de la ruta.

es decir edge_cost es igual a 1 / (peso máximo permitido del camión) el total_cost de una ruta dada es el máximo de los <=> individuales de todos los bordes en la ruta.

Answer 9

Varias respuestas anteriores proponen simplemente el algoritmo Dijkstra con una función de peso modificada. Por ejemplo, w(e) = -c(e) o 'w (e) = 1 / c (e)', donde w(e) es el peso de un borde, utilizado por el algoritmo, y c(e) es la capacidad del borde en el formulación original del problema.

Estos no funcionan.

Uno puede crear fácilmente contraejemplos de que esto produciría resultados incorrectos. Por ejemplo, considere el gráfico:

a---3-->b---3--->c---3-->d
 \                       ^
  \                      |
   \----------3----------|

Suponga que el valor de a ('distancia del nodo d en la formulación del algoritmo) es cero. Las dos rutas de (-3)+(-3)+(-3) = -9 a -3 son equivalentes en este problema. Sin embargo, si solo negamos la capacidad del borde, la distancia (d), usando la ruta larga, es (1/3)+(1/3)+(1/3)=1 mientras que usando la ruta corta sería (1/3). Si invertimos la capacidad del borde, la distancia (d) usando la ruta larga sería +, mientras que solo sería < usando la corta.

Lo que funcionará es modificar el paso de relajación del algoritmo, es decir, en lugar de usar las funciones de suma (min) y menor que (>), usando respectivamente las funciones <= > y mayor que (@), y use un montón máximo en lugar de un montón mínimo. Podríamos evitar las dos últimas modificaciones si negamos los pesos de los bordes y usamos menos que, pero de ninguna manera podemos evitar reemplazar a @ a = a, ya que necesitamos algún operador a=0 donde u para todos los valores d(u), mientras que <=> solo funciona para <=>.

Entonces, la única respuesta correcta que veo es la primera que da Keith Randall.

Un buen ejercicio sería probar formalmente que el algoritmo modificado es correcto. Lo que hay que demostrar es: - si <=> es el nodo con el valor máximo <=> en cualquier iteración de bucle, entonces ninguna ruta que involucre nodos sin marcar puede crear una ruta para <=> producir una distancia mayor que <=>.

Intuitivamente es fácil de ver, ya que todos los demás nodos sin marcar tienen una distancia menor que (o igual a) la distancia de 'u' (porque elegimos <=> como el que tiene la distancia máxima), y la distancia del las rutas generadas se producen mediante invocaciones sucesivas de <=>, por lo que solo puede hacerse más pequeño, no más grande.