Algoritmo de dijkstra
Páginas: 5 (1231 palabras)
Publicado: 25 de noviembre de 2010
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 origen al 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 consiste en ir explorandotodos 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.
Teniendo un grafo dirigidoponderado 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 nodoactual).
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 que la 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 + d(a,vi)
5. Marcamos como completo el nodo a.
6.Tomamos como próximo nodo actual el de menor valor en D (puede hacerse almacenando los valores en una cola de prioridad) y volvemos al paso 3 mientras existan nodos no marcados.
Una vez terminado al algoritmo, D estará completamente lleno.
Algoritmo de Dijkstra: Ejemplo
• Vértice origen 1.
• Aristas con trazo discontinuo = caminos provisionales desde el origen a los vértices.
• Aristas contrazo grueso = caminos mínimos ya calculados.
• Resto de aristas con trazo fino.
http://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra
http://mictlan.utm.mx/html/jaws/html/index9775.html?page/grafosdijkstra
ALGORITMO DE BELLMAN FORD
El algoritmo de Bellman-Ford (algoritmo de Bell-End-Ford), genera el camino más corto en un Grafo dirigido ponderado (en el que el peso de alguna de las aristaspuede ser negativo). El algoritmo de Dijkstra resuelve este mismo problema en un tiempo menor, pero requiere que los pesos de las aristas no sean negativos. Por lo que el Algoritmo Bellman-Ford normalmente se utiliza cuando hay aristas con peso negativo. Este algoritmo fue desarrollado por Richard Bellman, Samuel End y Lester Ford.
Este tipo de algoritmo era original de ruteo de la ARPANET. Sumodo de funcionamiento es el siguiente:
- Cada ruteador mantiene una tabla (un vector) que almacena las mejores distancias conocidas a cada destino y las líneas a usar para cada destino. Se actualizan las tablas intercambiando información con los vecinos.
- La tabla de un ruteador almacena una entrada para cada uno de los ruteadores en la subred (los ruteadores son los índices). Las entradasalmacenan la línea preferida de salida y una estimación del tiempo o la distancia al destino. Se pueden usar métricas distintas (saltos, retrasos, etc.).
- Cada ruteador tiene que medir las distancias a sus vecinos. Por ejemplo, si la métrica es el retraso, el ruteador la puede medir usando paquetes de eco.
- Cada T msegs los ruteadores intercambian sus tablas con sus vecinos. Un ruteadorusa las tablas de sus vecinos y sus mediciones de las distancias a sus vecinos para calcular una nueva tabla.
Ejemplo:
En la figura 1 se puede apreciar un grafo, donde los nodos A, B, C, D, E y F serán pueblos.
Figura 1. Pueblo A como punto de partida
En este caso, el pueblo inicial será el A. La distancia acumulada hasta ahora es 0 Km. Entonces, se procede a aplicar los tres pasos...
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 al 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 consiste en ir explorandotodos 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.
Teniendo un grafo dirigidoponderado 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 nodoactual).
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 que la 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 + d(a,vi)
5. Marcamos como completo el nodo a.
6.Tomamos como próximo nodo actual el de menor valor en D (puede hacerse almacenando los valores en una cola de prioridad) y volvemos al paso 3 mientras existan nodos no marcados.
Una vez terminado al algoritmo, D estará completamente lleno.
Algoritmo de Dijkstra: Ejemplo
• Vértice origen 1.
• Aristas con trazo discontinuo = caminos provisionales desde el origen a los vértices.
• Aristas contrazo grueso = caminos mínimos ya calculados.
• Resto de aristas con trazo fino.
http://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra
http://mictlan.utm.mx/html/jaws/html/index9775.html?page/grafosdijkstra
ALGORITMO DE BELLMAN FORD
El algoritmo de Bellman-Ford (algoritmo de Bell-End-Ford), genera el camino más corto en un Grafo dirigido ponderado (en el que el peso de alguna de las aristaspuede ser negativo). El algoritmo de Dijkstra resuelve este mismo problema en un tiempo menor, pero requiere que los pesos de las aristas no sean negativos. Por lo que el Algoritmo Bellman-Ford normalmente se utiliza cuando hay aristas con peso negativo. Este algoritmo fue desarrollado por Richard Bellman, Samuel End y Lester Ford.
Este tipo de algoritmo era original de ruteo de la ARPANET. Sumodo de funcionamiento es el siguiente:
- Cada ruteador mantiene una tabla (un vector) que almacena las mejores distancias conocidas a cada destino y las líneas a usar para cada destino. Se actualizan las tablas intercambiando información con los vecinos.
- La tabla de un ruteador almacena una entrada para cada uno de los ruteadores en la subred (los ruteadores son los índices). Las entradasalmacenan la línea preferida de salida y una estimación del tiempo o la distancia al destino. Se pueden usar métricas distintas (saltos, retrasos, etc.).
- Cada ruteador tiene que medir las distancias a sus vecinos. Por ejemplo, si la métrica es el retraso, el ruteador la puede medir usando paquetes de eco.
- Cada T msegs los ruteadores intercambian sus tablas con sus vecinos. Un ruteadorusa las tablas de sus vecinos y sus mediciones de las distancias a sus vecinos para calcular una nueva tabla.
Ejemplo:
En la figura 1 se puede apreciar un grafo, donde los nodos A, B, C, D, E y F serán pueblos.
Figura 1. Pueblo A como punto de partida
En este caso, el pueblo inicial será el A. La distancia acumulada hasta ahora es 0 Km. Entonces, se procede a aplicar los tres pasos...
Leer documento completo
Regístrate para leer el documento completo.