Diferencia entre revisiones de «Algoritmo de Dijkstra»
Contenido eliminado Contenido añadido
Sin resumen de edición |
m Revertidos los cambios de 200.82.55.108 (disc.) a la última edición de TXiKiBoT |
||
Línea 1:
[[Imagen:Dijksta_Anim.gif|thumb|283px|Ejecución del algoritmo de Dijkstra]]
El '''algoritmo de Dijkstra''', también llamado '''algoritmo de caminos mínimos''', es un [[algoritmo]] para la determinación del [[Problema de los caminos más cortos|camino más corto]] dado un [[Vértice (Teoría de grafos)|vértice]] origen al resto de vértices en un [[grafo]]
La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene. El algoritmo es una especialización de la búsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de costo negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).
| |||