Algortimo en retroceso

LABORATORIO

CURSO : Diseño y análisis de algoritmos

No. : Laboratorio No.10

TEMA : Algoritmo en Retroceso

DURACIÓN ESTIMADA : 01:40 horas.

I. OBJETIVOS

El presente laboratorio tiene por objetivos:

• Utilizar el IDE de Netbeans.

• Crear un proyecto para un caso de estudio.

• Construir y ejecutar una aplicación con múltiples clases.

II. RESUMEN

En esta práctica usted explorara un proyecto completo en Netbeans con múltiples clases y  asociación entre clases. Para ello desarrollaremos parcialmente el caso de estudio, enfocando  en desarrollar una solución óptima de un recorrido de un grafo con el camino más corto III. PROBLEMÁTICA

Recorrido de un grafo con el camino más corto

El problema consiste en encontrar la ruta más corta entre cualquier par de nodos de un grafo.  Sea el ejemplo de ir de v0 a v3

[pic 2]

Elaborar el algoritmo respectivo e implementarlo en un lenguaje de programación para realizar  las pruebas necesarias de su eficiencia

Solución

Para la solución de este problema utilizaremos el algoritmo de Dijkstra.

Función Dijkstra (Grafo G, nodo_salida s)

//Usaremos un vector para guardar las distancias del nodo salida al resto entero distancia[n]

//Inicializamos el vector con distancias iniciales booleano visto[n]

//vector de boleanos para controlar los vertices de los que ya  tenemos la distancia mínima

Para cada w ∈ V[G] hacer

Si (no existe arista entre s y w) entonces

distancia[w] = Infinito  //puedes marcar la casilla con un -1 por ejemplo

          Si_no

                    distancia[w] = peso (s, w)

              Fin si

  Fin para

  distancia[s] = 0

  visto[s] = cierto

  //n es el número de vertices que tiene el Grafo

 Mientras que (no_esten_vistos_todos) hacer

          vertice = coger_el_minimo_del_vector distancia y que no este visto;

          visto[vertice] = cierto;

Para cada w ∈ sucesores (G, vertice) hacer

                 Si distancia[w]>distancia[vertice]+peso (vertice, w) entonces

                           distancia[w] = distancia[vertice]+peso (vertice, w)

                         Fin si

                Fin para

  Fin mientras

  Fin función

Codificación en JAVA NETBEANS

[pic 3][pic 4]

[pic 5]

[pic 6]

Ejecución:

Si observamos para ir desde el V1 al V8

...