Ruta más corta en grafos: algoritmo supera a Dijkstra tras 65 años

Este problema, conocido como el problema de la ruta más corta u óptima, ha perseguido a la humanidad desde hace siglos. Por ejemplo, en el siglo III a.C. Euclides demostró que una línea recta era siempre más corta que cualquier camino quebrado. O en el siglo XI, astrónomos islámicos resolvían cálculos de geometría esférica para encontrar la qibla, la dirección más corta hacia La Meca desde cualquier punto del planeta.

[#1 Torrezzno]

Muy interesante. Lo leeré mañana con tranquilidad. La mayor utilidad que le he dado a Dijkstra es en los advent of code

Esto: O(m + n log n) equivale a esto O(nlogn) ya que siempre se coje el limite superior y se obvia el resto.

En wolfram alpha podeis ver la representación y como crece

www.wolframalpha.com/input?i=plot+n*log^(2/3)n,+plot+n*logn

Así se ve fácilmente que crece ligeramente más lento  

[#6 TripleXXX]

#1 Yo también lo de dejaré para mañana.
En el tipo de trabajo que hacía nunca tuve que resolver ese tipo de problemas, lo recuerdo de la universidad y veía complicado mejorarlo pero nunca puedes descartar el ingenio de algunas personas.

[#7 Tailgunner]

#1 en serio...?

[#10 Acido_1]

#1


> Esto: O(m + n log n) equivale a esto O(nlogn) ya que siempre se coje el limite superior y se obvia el resto.

No, me temo que te equivocaste pensando que "m" es una constante, como si fuese independiente de n... Pero NO.
El "m" es el número de aristas y si aumentas "n" debes aumentar "m", al menos en el contexto de Dijkstra que se trata de rutas y encaminamiento.

Si tienes "n" vértices, y si ningún vértice está desconectado,…   

[#2 pingON]

Dijkstra, supone la creación de un árbol ordenado, partiendo del nodo de origen y todos los posibles destinos que aparecen en el grafo.

Emplee Dijkstra Un ciudadano 'resuelve' la ecuación de la movilidad de Zaragoza: "¿Por qué tenemos siempre que delegar en los políticos?" y Zaragoza. Regalo 20 líneas de tranvía y 4.000 millones de razones

[#3 Torrezzno]

#2 te refieres a un B tree?
en.m.wikipedia.org/wiki/B-tree

Diskjtra es para grafos que es un tipo más general que los árboles ya que se permiten ciclos. Los nodos de un grafo no tienen un orden inherente, aunque los puedas recorrer en un orden concreto DFS por ejemplo.

[#5 pingON]

#3 Me refiero a que cuando haces Diskjtra, tomas el nodo de origen y vas construyendo un árbol, insertando cada uno de los nodos que aún no has añadido. y al hacer las insercciones de cada nuevo nodo queda ordenado según las distancias acumuladas. Ahora es muy tarde, pero recuerdo que cuando estuve haciendo ese desarrollo, es la imagen mental que me quedó y si lo haces sobre papel, es cómo te digo.

[#4 hrundil]

#3 creo que se refiere a que el resultado de ejecutar dijkstra es un árbol con el camino mínimo desde el nodo origen a todos los demás. Suponiendo un grafo conexo.

[#8 mcfgdbbn3]

Pues a ver si le ponen un nombre más sencillo de pronunciar.

[#9 maloconocido]

#8 Díselo a sus padres