Algoritmo de dijkstra
Páginas: 3 (616 palabras)
Publicado: 14 de septiembre de 2010
UNIVERSIDAD TECNOLÓGICA DE HONDURAS
INVESTTIGACIÓN ALGORITMO DE DIJKSTRA
Integrado por:
Mario Valladares 200660530043
Catedrático Marvin Mejía
Hecho en Tegucigalpa el 25 de Mayo del2010
LECTURA:
ALGORITMO DE DIJKSTRA
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 origenal resto de vértices en un grafo dirigido y con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.
La idea subyacente en este algoritmo consisteen 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érticesque 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 elegirsiempre 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).
EL ALGORITMO:Teniendo un grafo dirigido ponderado de N nodos no aislados, sea x el nodo inicial, un vector D de tamaño N guardará al final del algoritmo las distancias desde x al resto de los nodos.
1.Inicializar todas las distancias en D con un valor infinito relativo ya que son desconocidas al principio, exceptuando la de x que se debe colocar en 0 debido a que la distancia de x a x sería 0.
2. Sea a= x (tomamos a como nodo actual).
3. Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a estos vi.
4. Si la distancia desde x hasta vi guardada en D es mayor quela distancia desde x hasta a sumada a la distancia desde a hasta vi; esta se sustituye con la segunda nombrada, esto es:
si (Di > Da + d(a,vi)) entonces Di = Da +...
INVESTTIGACIÓN ALGORITMO DE DIJKSTRA
Integrado por:
Mario Valladares 200660530043
Catedrático Marvin Mejía
Hecho en Tegucigalpa el 25 de Mayo del2010
LECTURA:
ALGORITMO DE DIJKSTRA
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 origenal resto de vértices en un grafo dirigido y con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.
La idea subyacente en este algoritmo consisteen 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érticesque 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 elegirsiempre 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).
EL ALGORITMO:Teniendo un grafo dirigido ponderado de N nodos no aislados, sea x el nodo inicial, un vector D de tamaño N guardará al final del algoritmo las distancias desde x al resto de los nodos.
1.Inicializar todas las distancias en D con un valor infinito relativo ya que son desconocidas al principio, exceptuando la de x que se debe colocar en 0 debido a que la distancia de x a x sería 0.
2. Sea a= x (tomamos a como nodo actual).
3. Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a estos vi.
4. Si la distancia desde x hasta vi guardada en D es mayor quela distancia desde x hasta a sumada a la distancia desde a hasta vi; esta se sustituye con la segunda nombrada, esto es:
si (Di > Da + d(a,vi)) entonces Di = Da +...
Leer documento completo
Regístrate para leer el documento completo.