metodo de la ruta mas corta.
Páginas: 3 (692 palabras)
Publicado: 16 de mayo de 2013
MODELO DE LA RUTA MÁS CORTA
CONCEPTOS
El problema de la ruta más corta incluye un juego de nodos conectados donde sólo un nodo es considerado como el origen y sólo un nodo es consideradocomo el nodo destino. El objetivo es determinar un camino de conexiones que minimizan la distancia total del origen al destino. El problema se resuelve por el "algoritmo de etiquetado".
La esencia delprocedimiento es que analiza toda la red a partir del origen; identifica de manera sucesiva la ruta más corta a cada uno de los nodos en orden ascendente de sus distancias (más cortas), desde elorigen; el problema queda resuelto en el momento de llegar al nodo destino.
CARACTERISTICAS
Determina el camino más corto dado un vértice origen.
Utiliza un tipo de estructura decola llamado cola de prioridad.
ORIGEN DEL ALGORITMO DE DIJKSTRA Y EJEMPLO DE ESTE ALGORITMO
ORIGEN
El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmopara la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en1959.
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.Reescribimos la tabla del enunciado:
Y formulamos con los datos de la tabla nuestro grafo:
El nodo 7 y los caminos que conducen a el no son importantes en nuestro problema, puesto a que enel enunciado nos aclara que el horizonte de planeación es desde el inicio del 2001 (nodo 1)hasta fines del 2005(implícitamente inicios del 2006) (nodo 6). Es por esto que lo coloreamos de plomo, y nolo tomaremos en cuenta en el algoritmo.
Algoritmo dijkstra
Redibujamos nuestro grafo, para que se note mejor los pasos del algoritmo.(Recordar no considerar el nodo 7)Etiquetemos el nodo 1 con...
MODELO DE LA RUTA MÁS CORTA
CONCEPTOS
El problema de la ruta más corta incluye un juego de nodos conectados donde sólo un nodo es considerado como el origen y sólo un nodo es consideradocomo el nodo destino. El objetivo es determinar un camino de conexiones que minimizan la distancia total del origen al destino. El problema se resuelve por el "algoritmo de etiquetado".
La esencia delprocedimiento es que analiza toda la red a partir del origen; identifica de manera sucesiva la ruta más corta a cada uno de los nodos en orden ascendente de sus distancias (más cortas), desde elorigen; el problema queda resuelto en el momento de llegar al nodo destino.
CARACTERISTICAS
Determina el camino más corto dado un vértice origen.
Utiliza un tipo de estructura decola llamado cola de prioridad.
ORIGEN DEL ALGORITMO DE DIJKSTRA Y EJEMPLO DE ESTE ALGORITMO
ORIGEN
El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmopara la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en1959.
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.Reescribimos la tabla del enunciado:
Y formulamos con los datos de la tabla nuestro grafo:
El nodo 7 y los caminos que conducen a el no son importantes en nuestro problema, puesto a que enel enunciado nos aclara que el horizonte de planeación es desde el inicio del 2001 (nodo 1)hasta fines del 2005(implícitamente inicios del 2006) (nodo 6). Es por esto que lo coloreamos de plomo, y nolo tomaremos en cuenta en el algoritmo.
Algoritmo dijkstra
Redibujamos nuestro grafo, para que se note mejor los pasos del algoritmo.(Recordar no considerar el nodo 7)Etiquetemos el nodo 1 con...
Leer documento completo
Regístrate para leer el documento completo.