TALLER N.5 : ESTRUCTURA DE DATOS II

UNIVERSIDAD TECNOLÓGICA DE PANAMÁ

FACILTAD DE INGENIERÍA DE SISTEMAS COMPUTACIONALES

DEPARTAMENTO DE COMPUTACIÓN Y SIMULACIÓN DE SISTEMAS

ESTRUCTURA DE DATOS II

TALLER N°5: Algoritmo de grafo (1)

Profesoras:         Yolanda de Miguelena

Nombres:         Girón, Jorge 8-855-449

                González, Franklin 8-861-1864

Objetivo

        Resolver el problema de grafo utilizando el algoritmo de Dijkstra.

Enunciado

Dado el siguiente grafo con sus respectivos pesos, obtenga lo siguiente:

1. Calcule el algoritmo de Dijkstra.
2. Represente la matriz de adyacencia.

[pic 1]

A=

Q0 =

K=1

C= F, V

F=  No Hay

No Hay Relación

Q1 =                         1                 2                  3                    4                      5

K= 2

C= W

F= A, V

Relaciónes= (W,A) (W,V)

Q(W,A) = MIN { Q(W, A), Q(W,2) + Q(2,A) }

                      ∞        ,        4     +    5        =    9*

Q(W,V) = MIN { Q(W, V), Q(W,2) + Q(2,V) }

                      ∞        ,       4      +    5        =    9*

Q2 =

K = 3

C= No hay

F= W

No hay Relación

Q3 =

K=4

C= F, W

F= A

Relación = (F, A) (W, A)

Q(F,A) = MIN { Q(F, A), Q(F,4) + Q(4,A) }

                      5        ,    5     +    8        =    13

Q(W,A) = MIN { Q(W, A), Q(W,4) + Q(4,A) }

                      9        ,       9      +    8        =    17

Q4 =

K=5

C= L

F= A, F, V

Relación = (L, A) (L, F) (L,V)

Q(L,A) = MIN { Q(L, A), Q(L,5) + Q(5,A) }

                      ∞        ,    9     +    9        =    18*

...