alienaciopn
Páginas: 2 (359 palabras)
Publicado: 23 de noviembre de 2013
ALGORITMOS
Hay diferentes algoritmos para hallar un camino de longitud mínima entre dos vértices de un grafo ponderado. Presentaremos un algoritmo descubierto por el físico holandés EdsgerDijkstra en 1959. La versión que descubriremos resuelve este problema para grafos ponderados no dirigidos si todos los pesos no son negativos. Este algoritmo puede adaptarse fácilmente para resolver problemasde caminos de longitud mínima en grafo dirigidos
Ejemplos de algoritmos
Rojo: Aristas y vértices pertenecientes a la solución momentánea.
Azul: Aristas y vértices candidatos.
Paso 1
En DDistancia:5
Paso 2
Ahora, vemos que se añade un nuevo candidato, el vértice e, y el vértice c, pero esta vez a través del d. Pero el camino mínimo surge al añadir el vértice c.
Solución momentánea:camino:ADC distancia:9
Paso 3
En este paso se añade como candidato el vértice f. En este caso el camino mínimo hallado es el siguiente:
Solución momentánea:
Camino: ADCB
Distancia:11
Paso 4Como podemos comprobar, se han añadido un candidato nuevo, el vértice g, a través del vértice b. El mínimo camino hallado en todo el grafo hasta ahora es el siguiente:
Solución momentánea:
Camino:ADCBF
Distancia:15
Paso 5
En este antepenúltimo paso, se añaden tres vértices candidatos, los vértices g, z y e. Este último ya estaba pero en esta ocasión aparece a través del vértice f. Eneste caso el camino mínimo, que cambia un poco con respecto al anterior, es: SOLUCIÓN DE MOMENTANEA..Camino:ADCBG ..Distancia: 17
Paso 6
En el penúltimo paso, vuelve a aparecer otro candidato: elvértice e, pero esta vez a través del vértice f. De todas formas, el camino mínimo vuelve a cambiar para retomar el camino que venía siguiendo en los pasos anteriores:
Solución momentánea:
Camino:ADCBFE
Distancia:18
Paso 7
Por fin, llegamos al último paso, en el que sólo se añade un candidato, el vértice z a través del e. El camino mínimo y final obtenido es nada más y nada menos k:...
Hay diferentes algoritmos para hallar un camino de longitud mínima entre dos vértices de un grafo ponderado. Presentaremos un algoritmo descubierto por el físico holandés EdsgerDijkstra en 1959. La versión que descubriremos resuelve este problema para grafos ponderados no dirigidos si todos los pesos no son negativos. Este algoritmo puede adaptarse fácilmente para resolver problemasde caminos de longitud mínima en grafo dirigidos
Ejemplos de algoritmos
Rojo: Aristas y vértices pertenecientes a la solución momentánea.
Azul: Aristas y vértices candidatos.
Paso 1
En DDistancia:5
Paso 2
Ahora, vemos que se añade un nuevo candidato, el vértice e, y el vértice c, pero esta vez a través del d. Pero el camino mínimo surge al añadir el vértice c.
Solución momentánea:camino:ADC distancia:9
Paso 3
En este paso se añade como candidato el vértice f. En este caso el camino mínimo hallado es el siguiente:
Solución momentánea:
Camino: ADCB
Distancia:11
Paso 4Como podemos comprobar, se han añadido un candidato nuevo, el vértice g, a través del vértice b. El mínimo camino hallado en todo el grafo hasta ahora es el siguiente:
Solución momentánea:
Camino:ADCBF
Distancia:15
Paso 5
En este antepenúltimo paso, se añaden tres vértices candidatos, los vértices g, z y e. Este último ya estaba pero en esta ocasión aparece a través del vértice f. Eneste caso el camino mínimo, que cambia un poco con respecto al anterior, es: SOLUCIÓN DE MOMENTANEA..Camino:ADCBG ..Distancia: 17
Paso 6
En el penúltimo paso, vuelve a aparecer otro candidato: elvértice e, pero esta vez a través del vértice f. De todas formas, el camino mínimo vuelve a cambiar para retomar el camino que venía siguiendo en los pasos anteriores:
Solución momentánea:
Camino:ADCBFE
Distancia:18
Paso 7
Por fin, llegamos al último paso, en el que sólo se añade un candidato, el vértice z a través del e. El camino mínimo y final obtenido es nada más y nada menos k:...
Leer documento completo
Regístrate para leer el documento completo.