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.
|
etiquetas: grafos , ruta , matemáticas 
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
> 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,… » ver todo el comentario
Se puede explicar mejor así:
O(m + n log n) = O(m) + O(nlogn)
El número maximo de vértices que puede tener un nodo m en un grafo completo es: (n-1)×n = O(n^2)
En un grafo muy denso m podría darse
O(n^2) + O(nlogn). de nuevo cogiendo el limite superior sería una complejidad de O(n^2)
Entonces el nuevo algoritmo mejora a diskjtra tanto en el mejor como en el peor caso lo cual es decir muchisimo.
Se puede elegir una implementación u otra dependiendo del tamaño del grafo. De igual forma que leer un array es más rápido para buscar elementos que una tabla hash cuando el número de elementos es pequeño.
> Entonces el nuevo algoritmo mejora a diskjtra tanto en el mejor como en el peor caso lo cual es decir muchisimo.
Dijkstra
[Nota: tiene ijk , que son letras consecutivas en el abecedario, y que, además, son letras usadas como índices en sumatorios y algoritmos de programación... For i = 1... For j = ... For k = ...]
Y... NO, en el caso peor el nuevo algoritmo propuesto EMPEORA, no mejora al de Dijsktra, cuando n tiende a infinito.
El caso peor es m ~ n^2
O( n^2 • log^(2/3) n )
es peor que
O (n^2 + n log n) ~ O(n^2)
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.
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
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.
Problema resuelto. Ahora podemos centrarnos en arreglar tu nick
blog.smaldone.com.ar/2006/08/01/estimado-sr-x-de-la-empresa-y
¿No es "arista" un término un tanto confuso para lo que sería una "línea de conexión", o simplemente, un "conector"? Para mí (y la RAE) una arista es la línea de intersección entre dos planos. Que yo sepa, no hay planos en un grafo.
El artículo afirma sobre Dijkstra: "el algoritmo termina cuando todos los vértices han sido visitados". Pero el algoritmo realmente termina cuando el nodo a extraer de la lista temporal ordenada es la meta (o la lista está vacía), o en otra palabras, cuando no existe un nodo más cercano al origen que la propia meta.
arista
f. Línea que resulta de la intersección de dos planos.
dle.rae.es/arista
La intersección de esos dos planos está definida por dos puntos, en este caso los nodos del grafo.
De todas formas, aunque una arista sea siempre una línea no se puede deducir que una línea sea siempre una arista. Lo que en lógica formal se escribe: A→B ⇏ B→A
El algoritmo no termina cuando el nodo a extraer es la meta porque entonces no habrías explorado todos los caminos (SSSP completo)
De la wiki: El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto, dado un vértice origen, hacia el resto de los vértices.