Benjamin
Páginas: 3 (637 palabras)
Publicado: 8 de agosto de 2013
UNIVERSIDAD TECNOLÓGICA DE PANAMÁ
FACULTAD DE INGENIERÍA DE SISTEMAS COMPUTACIONALES
DEPARTAMENTO DE COMPUTACIÓN Y SIMULACIÓN DE SISTEMAS
ESTRUCTURAS DE DATOS II
Guía para resolver problemasdel camino mínimo utilizando el Algoritmo de Dijkstra
Objetivos
Identificar los pasos para obtener el camino mínimo con el algoritmo de Dijktra.
Resolver problemas para obtener el caminomínimo utilizando el algoritmo de Dijkstra.
I. PARTE
El algoritmo de Dijktra, encuentra el camino más corto de un vértice elegido a cualquier otro vértice de la gráfica, dondela longitud de un camino es la suma de los pesos de las aristas que lo formen. Los pasos para realizar el procedimiento son:
Aplicar el algoritmo de Warshall para cada iteración.
Siempre queexista una relación de un vértice intermedio se calcula la función Min para cada relación que exista.
Reemplazar el mínimo valor en la relación que fue calculada.
Continuar con la siguienteiteración y repetir los mismos pasos hasta llegar al último vértice intermedio a evaluar.
II. PARTE
Ejemplo que muestra el procedimiento de cómo utilizar el algoritmo de Dijktra.Obtener la matriz de adyacencia
Generar la Matriz Q0 a partir de la matriz de Adyacencia
Se copia la misma matriz pero ahora con el nombre Q.Generar la Matriz Q1 a partir de la matriz Q0
La K nos indica en qué columna y fila nos debemos parar para escoger las posiciones que sean diferentes de ceros. Se evalúan la fila y la columna 1 yaque K = 1.
K = 1 (2 = b, 3 = c)
j = 0
i = 2, 3
NO HAY VERTICE INTERMEDIO
En esta iteración no hayvértice intermedio puesto que no se generó ninguna relación.
Generar la Matriz Q2 a partir de la matriz Q1
Se evalúan la fila y la columna 2 ya que K = 2
K = 2...
FACULTAD DE INGENIERÍA DE SISTEMAS COMPUTACIONALES
DEPARTAMENTO DE COMPUTACIÓN Y SIMULACIÓN DE SISTEMAS
ESTRUCTURAS DE DATOS II
Guía para resolver problemasdel camino mínimo utilizando el Algoritmo de Dijkstra
Objetivos
Identificar los pasos para obtener el camino mínimo con el algoritmo de Dijktra.
Resolver problemas para obtener el caminomínimo utilizando el algoritmo de Dijkstra.
I. PARTE
El algoritmo de Dijktra, encuentra el camino más corto de un vértice elegido a cualquier otro vértice de la gráfica, dondela longitud de un camino es la suma de los pesos de las aristas que lo formen. Los pasos para realizar el procedimiento son:
Aplicar el algoritmo de Warshall para cada iteración.
Siempre queexista una relación de un vértice intermedio se calcula la función Min para cada relación que exista.
Reemplazar el mínimo valor en la relación que fue calculada.
Continuar con la siguienteiteración y repetir los mismos pasos hasta llegar al último vértice intermedio a evaluar.
II. PARTE
Ejemplo que muestra el procedimiento de cómo utilizar el algoritmo de Dijktra.Obtener la matriz de adyacencia
Generar la Matriz Q0 a partir de la matriz de Adyacencia
Se copia la misma matriz pero ahora con el nombre Q.Generar la Matriz Q1 a partir de la matriz Q0
La K nos indica en qué columna y fila nos debemos parar para escoger las posiciones que sean diferentes de ceros. Se evalúan la fila y la columna 1 yaque K = 1.
K = 1 (2 = b, 3 = c)
j = 0
i = 2, 3
NO HAY VERTICE INTERMEDIO
En esta iteración no hayvértice intermedio puesto que no se generó ninguna relación.
Generar la Matriz Q2 a partir de la matriz Q1
Se evalúan la fila y la columna 2 ya que K = 2
K = 2...
Leer documento completo
Regístrate para leer el documento completo.