Algoritmo Dijkstra

Algoritmo Dijkstra

1. ALGORTIMO DIJKSTRA

2. E l A l g o r t i m o d e D i j k s t r a , t a m b i é n d e n o m i n a d o A l g o r i t m o d e c a m i n o s mínimos, es un modelo que se clasifica d e n t r o d e l o s a l g o r i t m o s d e b ú s q u e d a . S u o b j e t i v o , e s d e t e r m i n a r la r u t a m á s c o r t a , d e s d e e l n o d o o r i g e n , h a s t a cu a l q u i e r n o d o d e la r e d . Definición

3. Características S e u t ili z a p a r a e n c o n t r a r e l c a m i n o m á s c o r t o entre dos nodos No tiene información previa sobre el grafo o el c a m i n o m á s c o r t o , v a e x p l o r a n d o e l g r a f o h a s t a e n c o n t r a r e l c a m i n o . U t ili z a la c o la d e p r i o r i d a d p a r a a l m a c e n a r n o d o s v i s i t a d o s y p r i o r i z a r l o q u e t i e n e n m e n o r corto A s i g n a u n c o s t o a c a d a a r c o o a r i s t a e n e l g r a f o E s u n a l g o r i t m o d e t i e m p o c o m p l e j o O ( E l o g V ) p a r a g r a f o s n o d i r i g i d o s y O ( V ^ 2 ) p a r a g r a f o s dirigidos, donde E es el número de arcos y V es e l n ú m e r o d e v é r t i c e s e n e l g r a f o .

4. E l a l g o r i t m o d e D i j k s t r a h a c e u s o y d e f i n e etiquetas a partir del nodo origen y para c a d a u n o d e l o s n o d o s s u b s i g u i e n t e s . E s t a s etiquetas contienen información relacionada con un valor acumulado del tamaño de los arcos y con la procedencia m á s p r ó x i m a d e la r u t a . ¿Cómo funciona?

5. La función    implementa el algoritmo de Dijkstra para encontrar el camino más corto desde un nodo origen a todos los demás nodos en un grafo ponderado no dirigido representado por una lista de adyacencia .

6. B I B L I O G R A F I A Cifuentes M, C., & Profile, V. M. C. (s. f.). Teoría de Grafos: GRAFOS BIPARTIDOS. http://teoriadegrafos.blogspot.com/2007/03/grafos-bipartidos.html EcuRed. (s. f.). Grafo bipartido - EcuRed. https:// www.ecured.cu/Grafo_bipartido Jesus, D. de. (s. f.). Grafo bipartito. https://es.slideshare.net/DukakisdeJesus/grafo-bipartito- 15542624 López, B. S. (2019, 28 octubre). Algoritmo de Dijkstra. Ingenieria Industrial Online. https:// www.ingenieriaindustrialonline.com/investigacion-de-operaciones/algoritmo-de-dijkstra/ El algoritmo de Dijkstra - Los caminos más cortos con el algoritmo de Dijkstra. (s. f.). CodinGame. https:// www.codingame.com/playgrounds/7656/los-caminos-mas-cortos-con-el- algoritmo-de-dijkstra/el-algoritmo-de-dijkstra