marcoyel21
commented
1 year ago Se añade una descripción muy sencilla, podriamos añadir un pseudocódigo del algoritmo pero como prefieran.
Se añadió lo siguiente:
Algoritmo Dijkstra
El algoritmo de Dijkstra sirve para encontrar el camino más corto entre dos nodos de un grafo. Encuentra la distancia más corta entre un nodo particular y todos los demás nodos, creando un "arbol de distancia mas corta". Es de gran utilidad por ejemplo para los casos de redes muy pobladas (piensen en cadenas de suministro, redes sociales etc) y se usa por ejemplo en los GPS.
Como curiosidad, fue inventado por Dr. Dijkstra durante una cita en la que se preguntaba cuál era la mejor manera de llegar de Rotterdam a Groningen. Además menciona que le tomo diseñarlo 20 minutos y que parte escencial de su exito es su simpleza; menciona que no usó lapiz y pluma, de lo contrario,menciona, se hubiese vuelto innecesariamente más complejo.
Algoritmo:
Se comienza en el nodo fuente y se va analizando cada distancia al nodo adyacente. Se almacena la distancia más corta encontrada hasta el momento Se continua con el siguiente nodo más adjacente, se evalúa la distancia y se actualizan las distancias mínimas en caso de econtrarse una distancia más corta. Se repite hasta visitar el nodo más lejano.
Comentarios:
- Es masomenos un algoritmo de fuerza bruta pues tiene que visitar toda la gráfica (en el peor de los casos) partiendo de un nodo para conocer la distancia más corta.
- Los pesos de las aristas tienen que ser positivos de lo contrario no funciona aunque podemos resolver esto si hacemos una transformación a los pesos (como multiplicar al cuadrádo o tomar el valor absoluto dependiendo del contexto)
Fuentes https://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra https://www.freecodecamp.org/news/dijkstras-shortest-path-algorithm-visual-introduction/
jgarciad
Explicar el algoritmo y su funcionamiento de manera teórica.