ciencia: comentarios [4087126]

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

Shinu — Sat, 16 Aug 2025 13:49:01 +0000

#15 El diccionario de la RAE no es muy útil para estos temas, al fin y al cabo no es una enciclopedia.
Por ejemplo, la definición de dinosaurio es: Reptil fósil de gran tamaño, con cabeza pequeña, cuello largo, cola robusta y larga, y, en general, extremidades posteriores más largas que las anteriores.

» autor: Shinu

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

mcfgdbbn3 — Sat, 16 Aug 2025 10:20:54 +0000

#13: Si me banean el suficiente número de veces y sigo poniendo el nombre al azar, llegará un momento en que salga algo fácilmente pronunciable y recordable.

» autor: mcfgdbbn3

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

Harkon — Sat, 16 Aug 2025 09:37:13 +0000

#29

» autor: Harkon

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

emptyboxa — Fri, 15 Aug 2025 20:24:45 +0000

#11 Joder, me has hecho loguearme después de meses con eso de la "complejidad ciclomática".

Eso es un número entero que mide la complejidad en términos de ramificación y repetición en un algoritmo o trozo de código...

PD: ¿Quién coño mete una constante en una expresión de O grande?

» autor: emptyboxa

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

atxesun — Fri, 15 Aug 2025 18:31:31 +0000

#28 Sí, claro, es indiscutiblemente una línea. Lo que no atiende a su definición es que sea una arista (línea que resulta de la intersección de dos planos). Es llamada así por tradición, por una inafortunada analogía, por una mala traducción o por lo que sea. Bien se le podría haber llamado simplemente línea, o segmento, o conexión, pero la tradición es la tradición y a ver quien osa decir que es una nomenclatura poco acertada. ¡Válgame dios!

» autor: atxesun

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

Harkon — Fri, 15 Aug 2025 18:01:24 +0000

#25 Pero una arista es una linea ergo la arista de A a B es una linea de A a B, aquí no hay una linea que sea una arista es que se la llama arista y significa linea por tanto ya te lo dicen todo

» autor: Harkon

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

pingON — Fri, 15 Aug 2025 16:19:18 +0000

#26 muchas gracias !!!

y por su puesto que NO, esta es una casa decente, aquí sólo hacemos las cosas cuando hay $obr€$ de por medio ......

» autor: pingON

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

SON_ — Fri, 15 Aug 2025 16:17:04 +0000

#2 toda mi admiración .
¿Se está llevando a cabo tu propuesta?

» autor: SON_

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

atxesun — Fri, 15 Aug 2025 11:26:06 +0000

#23 Como ya me han dicho que se le llama arista por tradición, no tengo nada más que decir aunque no compute semánticamente.

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

» autor: atxesun

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

Acido_1 — Fri, 15 Aug 2025 11:25:31 +0000

#11

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

» autor: Acido_1

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

Harkon — Fri, 15 Aug 2025 10:49:38 +0000

#15 Mmm según la RAE es correcto ya que es una linea

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.

» autor: Harkon

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

zancudo — Fri, 15 Aug 2025 10:02:54 +0000

#21 sí, pero esto no son conceptos geométricos sino de teoría de grafos, aunque usen la misma palabra por analogía

» autor: zancudo

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

atxesun — Fri, 15 Aug 2025 08:54:41 +0000

#19 Bueno, no es solo la RAE, es geometría.

» autor: atxesun

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

atxesun — Fri, 15 Aug 2025 08:50:19 +0000

#18 Vale, ya entiendo que se trata de encontrar el camino menos costoso a todos y cada uno de los vértices. Disculpa mi torpeza.

_{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.}

» autor: atxesun

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

zancudo — Fri, 15 Aug 2025 08:25:33 +0000

#15 olvídate de la RAE para términos técnicos

» autor: zancudo

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

A145236 — Fri, 15 Aug 2025 08:20:58 +0000

#15 es el lenguaje que se usa en teoría de grafos desde que se inventó y se habló de ello en español. Nodos (o vértices) y aristas.

El algoritmo no termina cuando el nodo a extraer es la meta porque entonces no habrías explorado todos los caminos (SSSP completo)

» autor: A145236

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

tommyx — Fri, 15 Aug 2025 07:47:26 +0000

#14 de naranja o limón?

» autor: tommyx

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

tommyx — Fri, 15 Aug 2025 07:46:38 +0000

#8 toda la razón mcfgdbbn3

» autor: tommyx

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

atxesun — Fri, 15 Aug 2025 07:22:39 +0000

Desde mi nula educación formal en estos temas y mi condición de aficionadillo me asaltan varias cuestiones:
¿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.

» autor: atxesun

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

robustiano — Fri, 15 Aug 2025 06:27:42 +0000

Como anéctoda, el tito Edsger se permitió en su día enviar a tomar Fanta a la mismísima IBM:

blog.smaldone.com.ar/2006/08/01/estimado-sr-x-de-la-empresa-y

» autor: robustiano

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

maxmalkav — Fri, 15 Aug 2025 06:13:47 +0000

#8 “daikstra”

Problema resuelto. Ahora podemos centrarnos en arreglar tu nick

» autor: maxmalkav

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

Torrezzno — Fri, 15 Aug 2025 05:29:09 +0000

#11 de hecho se ve en la gráfica, a partir de n=3 ya crece mas lento. Por lo que podría usarse de forma general

» autor: Torrezzno

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

Torrezzno — Fri, 15 Aug 2025 05:23:08 +0000

#10 tienes razón. Hablé sin haber hecho el análisis de la complejidad ciclomatica.y pensé que era una constante.

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.

» autor: Torrezzno

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

Acido_1 — Fri, 15 Aug 2025 04:20:54 +0000

#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, tendrás que tener mínimo m = n-1 aristas para conectar los n vértices.

Y el máximo m en grafos dirigidos es n^2 si admitimos que un vértice esté conectado a sí mismo, o bien, n•(n-1) si no lo permitimos.
Entonces,
O(m + n log n) estaría entre:

Mínimo : O(n-1 + n log n) ~ O(n log n)
Máximo : O(n^2 + n log n ) ~ O(n^2)

Luego, en tu comparativa de Wolfram has cambiado "m" por n... Pero, como dije antes, m podría ser del orden de n^2 ... aunque es cierto que si es del orden de n^2 resulta que el nuevo algoritmo es peor.
O(n^2 • log^(2/3) n) > O(n^2)

Pero si m es cercano a n resulta lo que dijiste:

Dijkstra: ~ O(n log n)

Nuevo: ~ O( n • log^(2/3) n)

El nuevo tendría orden de complejidad más bajo, y, por tanto, mejor. Aunque es posible que la mejora solo se notase para n muy grande... es decir, es posible que para los casos prácticos que usamos hoy la mejora casi ni se note.

A efectos teóricos me parece un gran logro, pero a efectos prácticos... mejor una mejora que no tenerla, pero no sería espectacular.

» autor: Acido_1

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

maloconocido — Fri, 15 Aug 2025 03:09:41 +0000

#8 Díselo a sus padres

» autor: maloconocido

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

mcfgdbbn3 — Fri, 15 Aug 2025 01:07:48 +0000

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

» autor: mcfgdbbn3

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

Tailgunner — Thu, 14 Aug 2025 23:33:29 +0000

#1 en serio...?

» autor: Tailgunner

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

TripleXXX — Thu, 14 Aug 2025 23:04:28 +0000

#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.

» autor: TripleXXX

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

pingON — Thu, 14 Aug 2025 22:32:51 +0000

#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.

» autor: pingON

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

hrundil — Thu, 14 Aug 2025 22:29:47 +0000

#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.

» autor: hrundil

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

Torrezzno — Thu, 14 Aug 2025 21:51:09 +0000

#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.

» autor: Torrezzno

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

pingON — Thu, 14 Aug 2025 21:44:08 +0000

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

» autor: pingON

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

Torrezzno — Thu, 14 Aug 2025 21:43:34 +0000

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

» autor: Torrezzno