¿Hay algoritmos más rápidos que Dijkstra?

Dado un gráfico dirigido y conectado con solo pesos de borde positivos, ¿hay algoritmos más rápidos para encontrar la ruta más corta entre dos vértices, que Dijkstra usando un montón de fibonacci?¿Hay algoritmos más rápidos que Dijkstra?

Wikipedia dice que Dijkstra está en O (| E | + | V | * log (| V |)) (utilizando un montón de fibonacci).

No estoy buscando optimizaciones que, por ejemplo, la mitad del tiempo de ejecución, sino algoritmos que están en una complejidad de tiempo diferente (como pasar de O (n * log n) a O (n)).

Además, me gustaría saber su opinión sobre el siguiente enfoque:

Determine el MCD de todos los pesos de las aristas.
Transforme el gráfico en un gráfico con pesos de borde uniformes.
Usa BFS para encontrar la ruta más corta entre dos vértices dados.

Ejemplo para el punto 2:
Imagine el GCD ser 1. Entonces me transformar el borde
A ---> B (peso borde 3)
en
A-> A '-> A' '-> B (3 veces el peso del borde 1)
Esta transformación cuesta un tiempo constante y tendría que hacerse una vez por cada borde. Así que espero que este algoritmo esté en O (| E |) (transformación) + O (| E | + | V |) (BFS) = O (2 * | E | + | V |) = O (| E | + | V |)

Gracias por tomarse el tiempo para leer mi pregunta y espero no haberle quitado el tiempo ^^. Que tengas un buen día.

Fuente

2009-11-09 Dave O.

Creo que te olvidas de contabilizar el costo del GCD. –

La transformación no se ejecuta en tiempo constante. Tendrás que crear una cantidad variable de nuevos vértices. –

El GCD sería el mejor valor para usar, pero uno siempre puede recurrir y usar solo 1, de modo que no se gasta tiempo en el paso 1. –

El gran análisis de oh que hizo para su algoritmo es profundamente defectuoso. Suponga que todos los bordes son números primos. El número de aristas en el nuevo gráfico será igual a la suma de todos los pesos. Por lo tanto, O(|E| + |V|) del nuevo gráfico es en realidad O(W x |E| + |V|) en el gráfico original que puede ser mucho más grande que O(|E| + |V| log |V|).

Fuente

2009-11-09 14:22:11

Tiene razón. En el peor de los casos, todos los pesos de los bordes son números primos y el gráfico está completo. Por lo tanto, W es al menos | V |^2 (| V |^2 bordes con pesos> = 1). Entonces mi algoritmo se ejecuta en | V |^2 * | V |^2 + | E | = | V |^4 + | E | al menos. Sin embargo, mi pregunta original sigue sin respuesta. –

Sry, quise decir | V |^4 + | V | - ¿Por qué no puedo editar mi publicación o mis comentarios? –

No estoy seguro de si hay un algoritmo asintóticamente más rápido para gráficos arbitrarios. El más rápido que sé es Dijkstra con montones de Fibonacci. No puedo estar seguro sin embargo. –

Hay un algoritmo que tiene O (1): convierte los pesos en longitudes de cadena y utiliza llaveros para los nodos (llaveros reales como los que tienes en el bolsillo). Conecte los llaveros con las cadenas correctas. Seleccione los dos nodos y jálelos el uno del otro.

Siga las cadenas tensas de un nodo a otro. Este es el camino más corto.

Para implementar esto como un programa de ordenador, tendrá dos robots industriales :)

Para una mayor ejemplo del mundo real, utilice el Ant colony optimization que da muy buenos resultados en un corto período de tiempo. Dado que puede especificar el número de ejecuciones en este algoritmo, puede decidir cuánto tiempo pasó (es decir, el tiempo de ejecución solo depende del número de nodos), lo que le otorga O (n) pero no garantiza un resultado perfecto.

Fuente

2009-11-09 14:35:41

¿Cómo es eso O (1)? –

Puedo pensar realmente en un algoritmo O (L), donde L es la cantidad de nodos en la solución correcta: quantum-bogo-shortest-path (http://en.wikipedia.org/wiki/Bogosort#Quantum_Bogosort) –

Is es O (1) si no considera el paso de creación de gráficos. – mouviciel

¿Hay algoritmos más rápidos que Dijkstra?

Sí. La pregunta no está calificada para exigir un mejor rendimiento en todos los casos, o incluso en la mayoría de los casos. Un algoritmo con un mejor rendimiento en un solo caso es suficiente para establecer una respuesta afirmativa.

A pesar de la generalmente mayor número de iteraciones requeridas por el método Bellman-Ford sobre el método de Dijkstra, en la práctica el método de Bellman-Ford puede ser superior debido a la sobrecarga más pequeña por iteración [oro, B., 1976 . "Algoritmos de ruta más corta: una comparación", Operations Research, vol. 44, pp. 1164-1168].

La cita anterior es de Dimitri P. Bertsekas (marzo de 1992). "Un algoritmo de corrección de etiquetas simple y rápido para rutas más cortas" (PDF). Redes, vol. 23, págs. 703-709, 1993. http://www.mit.edu/people/dimitrib/SLF.pdf. Consultado el 2008-10-01.

En resumen, mi afirmación se basa en la interpretación de Golden de Bertsekas. Independientemente de si mi conclusión se mantiene o no, puede encontrar a Bertsekas interesante por su clasificación del algoritmo de Dijkstra como como ajuste de etiqueta, en contraste con métodos de corrección de etiquetas.

Fuente

2009-11-09 14:52:33

Preguntó específicamente acerca de soluciones con menor tiempo de ejecución asintótica. –

OK, así que trátalo como un lema en el camino hacia el resultado final. –

En primer lugar, los resultados sobre lo que es más rápido "en la práctica" no son relevantes para lo que tiene * mejor crecimiento * asintóticamente, porque los gráficos encontrados en la práctica son finitos y generalmente pequeños. Además, más rápido en 1976 no se traduce necesariamente en más rápido en 2009. Por un lado, los gráficos "en la práctica" son más grandes hoy en día - para tomar un ejemplo exagerado, '200x^2' es cuatro veces más rápido que' n^3' para n = 50, pero un quinto como lento para n = 1000. – ShreevatsaR

Siempre hay A *, y sus derivados son Hierarchical A * y A * JPS.

Fuente

2012-07-01 01:48:37 Puppy

Creo que A * depende de que haya algún tipo de heurística significativa para decir cuál podría ser la mejor ruta. – mwfearnley

¿Hay algoritmos más rápidos que Dijkstra?

Respuesta

Cuestiones relacionadas