Proyecto

Implementación eficiente de los algoritmos para Grafos de Dijkstra y Floyd

      El objetivo de este proyecto es darle la oportunidad de comparar implementar eficientemente dos algoritmos para grafos que permiten calcula el costo m¡nimo de los cominos en un grafo: Dijkstra y Floyd. En lugar de utilizar una matriz N×N para amacenar los arcos del grafo, usted usará una lista de adyacencia implementada como en un vector, en donde los vértices de los arcos estén ordenados por número de vértice.

 /===\  4.5  /===\
 | A0 |----->| B1 |
 \===/     __\===/
   |        /|
   |       /
   |3.5   /
   |     /
   |    / 8.3
   |   /
  \|/ /
 /===\  7.2  /===\
 | C2 |<-----| D3 |
 \===/       \===/

    +---+        +-----+---+
 A  | 0 | -----> | 4.5 | 1 |
    +---+        +-----+---+
 B  | 2 |        | 3.6 | 2 |
    +---+        +-----+---+
 C  | 2 | -----> | 8.3 | 1 |
    +---+        +-----+---+
 D  | 3 | -----> | 7.2 | 2 |
    +---+        +-----+---+
    | 4 |
    +---+

      Esta representación es similar a la expuesta en el libro de texto del curso, en la figura 6.5. Sin embargo, aquí se omite usar un valor CERO para marcar el final de cada lista de adyacencia.

Aho, Alfred V.; Hopcroft, John E.; Ullman, Jefrrey D.

"Data Structures and Algorithms"; Addisson Wesley Publishing Co.; 1984.

      Su programa debe estar escrito en el lenguaje Pascal o en C++. Debe poner especial cuidado para lograr que el acceso a los vértices sea una operación que cueste tiempo O(1) para los algoritmos de Dijkstra y Floyd, aunque en general el tiempo de acceso para obtener un vértices se O(log n). Usted debe ajustar el Rep de su estructura de datos de manera que la eficiencia de estos dos algoritmos o sea comprometida.

PROCEDURE Floyd (
  VAR A: ARRAY[1..n, 1..n] OF REAL;
  VAR C: ARRAY[1..n, 1..n] OF REAL
);
{ Floyd computes shortest path matrix A given arc cost matrix C }
VAR
  i, j, k: INTEGER;
BEGIN
  FOR i := 1 TO n DO BEGIN
    FOR j := 1 TO  n DO BEGIN
      A[i, j] := C[i, j];
    END;
  END;

  FOR i := 1 TO n DO BEGIN
    A[i, i] := 0;
  END;
  FOR k:= 1 TO  n DO
    FOR i := 1 TO  n DO
      FOR j:= 1 TO  n DO
        IF A[i, k] + A[k, j] < A [i, j] THEN BEGIN
          A[i, j] := A[i, k] + A[k, j];
        END;
      END;
    END;
  END;
END; { Floyd }

PROCEDURE Dijkstra;
{ Dijkstra computes the cost of the shortest paths
  from vertex 1 to every vertex of a directed graph }
BEGIN
  S := {1};
  FOR i := 2 TO n DO
    D[i] := C[1, i]; { initialize D }
  END;

  FOR i := 1 TO n-1 DO  BEGIN
    choose a vertex w in V-S such that D[w] is a minimum;
    add w TO  S;
    FOR each vertex v in V-S DO  BEGIN
      D[v] := min(D[v], D[w] + C[w, v]);
    END;
  END;
END; { Dijkstra }

      Para verificar experimentalmente que su estructura de datos es tan eficente como una representación usando un matriz de adyacencia N×N, usted implementará también los algoritmos de Dijkstra y Floyd usando una matriz cuadrada, y medirá comparará los tiempos de ejecución de manera que pueda usted cotegar los tiempos de corrida de ambas implementaciones. (Por supuesto, también cotege que las dos versiones de cada algoritmo producen los mismos resultados).

      En su reporte escrito, además de los programas y la documentación que es costumbre entregar, incluya un análisis teórico que muestres las bondades de su estructura de datos respecto de la tradicional matriz de adyacencia.

      La comparación del rendimiento de varios algoritmos debe hacerse cuidadosamente pues de lo contrario se pueden presentar problemas de medición. Por eso, al desarrollar este proyecto, se debe usar una buena metodología. A fin de cuentas, usted debe entregar un reporte de investigación que contenga, al menos, los siguientes puntos:

1. Implementación de los algoritmos a comparar.
2. Análisis teórico de los algoritmos a comparar.
3. Justificación del tipo de comparación a realizar.
4. Definición del ambiente computacional en que se corrieron las pruebas.
5. Definición del tamaño de la matriz usada en cada prueba.
6. Cuadros y gráficos comparativos de desempeño.
7. Análisis e interpretación de los resultados.

Di Mare, Adolfo

Reutilización de Contenedores Parametrizables con Lenguajes de Semántica Limitada, Tesis de Doctorado, Universidad Autónoma de Centro América. 1999.
      http://www.di-mare.com/adolfo/binder

      El reporte de investigación debe ser entregado en clase, impreso. Además, también debe enviar todo el material a los asistentes del curso por correo electrónico. Para esto, haga un archivo empacado .zip cuyo nombre sea su número de carnet. Incluya en ese archivo lo siguiente:

1. Un documento en formato HTML que describa el trabajo que realizó. Incluya el nombre del compilador que usó.
2. El código fuente de su programa.
3. El código ejecutable de su programa.

      Después de la fecha de entrega del programa, puede usted instalar en su cuenta personal su solución (no instale antes su solución en Internet, pues en ese caso sería usted culpable de facilitar la copia de su trabajo, y en consecuencia se haría acreedor a la sanción respectiva).

      Las cuentas de computador en la ECCI se asignan de acuerdo al número de carnet. Por ejemplo, si su carnet es el número 95-28-09, para entregar su tarea usted debe crear el archivo 952809.zip para enviarlo por correo electrónico a los asistentes del curso. ños

      Luego haga en su cuenta personal un subdirectorio llamado public_html, que es bajo el que se instalan todas sus páginas Internet. Por ejemplo, si su solución está en el archivo HTML llamado "OLP/t3sol952809.htm", entonces usted debe instalar esa página en el archivo
      public_html/OLP/t3sol952809.htm
de su cuenta. Luego, para acceder esa página Internet, debe entrar a este sitio:
      http://anubis.ecci.ucr.ac.cr/~e952809/OLP/t3sol952809.htm

      Como todas las cuentas de estudiante son la letra "e" seguida del número de carnet, para el estudiante de carnet "952809" la cuenta es "e952809". Para indicarle al servidor Internet a cuál cuenta entrar se usa el caracter "~" (Alt-126), seguido del nombre de la cuenta: "~e952809".

Marilyn Bolaños y Mario Tenorio

Tiempo de entrega: Cuatro semanas Modalidad: Individual

Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 1999
Derechos de autor reservados © 1999