Lập trình

III.1 Bài tóan

Cài đặt chương trình thuật tóan Floyd –Warshall tìm đường đi ngắn nhất ở mọi cặp đỉnh giữa mọi cặp đỉnh bằng ngôn ngữ C.

File cấu trúc dữ liệu vào FLOYDWAR.INF có cấu trúc

n                      m                                 n: số đỉnh, m: số cung, a: đỉnh đầu, e: đỉnh cuối

                                               đỉnh đầu, đỉnh cuối, trọng số

                                     

 

^{………………}

                                     

 

^{…………………….}

q                      p                                  số đỉnh,số cung, đỉnh đầu, đỉnh cuối

                                                đỉnh đầu, đỉnh cuối, trọng số

                                      

^{………………}

                                     

^{…………………….}

 

File kết quả: FLOYDWAR.OUT

D  (Ma trận độ dài đường đi ngắn nhất giữa mọi cặp đỉnh)

……….

P (Ma trận xác định đường đi ngắn nhất giữa mọi cặp đỉnh)

Ví dụ:

	FLOYWAR.INP   FLOYWAR.OUT 4 7       17 7 5 13 1 2 7     10 7 7 6 1 3 5     15 12 19 11 2 3 7     4 1 8 7 2 4 6     -------------------------- 3 4 11     2 2 3 2 4 1 4     4 4 3 4 4 2 1     4 4 4 4           4 2 2 2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

#include <stdio.h>

intn; /* Then number of nodes */

intdist[16][16]; /* dist[i][j] is the length of the edge between i and j if

                       it exists, or 0 if it does not */

voidprintDist() {

        int i, j;

        printf("    ");

        for (i = 0; i < n; ++i)

            printf("%4c", 'A' + i);

        printf("\n");

        for (i = 0; i < n; ++i) {

               printf("%4c", 'A' + i);

               for (j = 0; j < n; ++j)

                       printf("%4d", dist[i][j]);

               printf("\n");

        }

        printf("\n");

}

/*

        floyd_warshall()

        after calling this function dist[i][j] will the the minimum distance

        between i and j if it exists (i.e. if there's a path between i and j)

        or 0, otherwise

*/

voidfloyd_warshall() {

        int i, j, k;

        for (k = 0; k < n; ++k) {

               printDist();

               for (i = 0; i < n; ++i)

                       for (j = 0; j < n; ++j)

                               /* If i and j are different nodes and if 

                                      the paths between i and k and between

                                      k and j exist, do */

                               if ((dist[i][k] * dist[k][j] != 0) && (i != j))

                                      /* See if you can't get a shorter path

                                              between i and j by interspacing

                                              k somewhere along the current

                                              path */

                                      if ((dist[i][k] + dist[k][j] < dist[i][j]) ||

                                              (dist[i][j] == 0))

                                              dist[i][j] = dist[i][k] + dist[k][j];

        }

        printDist();

}

intmain(int argc, char *argv[]) {

        FILE *fin = fopen("dist.txt", "r");

        fscanf(fin, "%d", &n);

        int i, j;

        for (i = 0; i < n; ++i)

               for (j = 0; j < n; ++j)

                       fscanf(fin, "%d", &dist[i][j]);

        fclose(fin);

        floyd_warshall();

        return 0;

}

 

II.2. Cài đặt bằng ngôn ngữ C/Java

 

// Floyd-Warshall algorithm - iterative version

//

// Author: Nguyen Minh Nhat

// Ngay: 04,2018 .

public class FloydWarshallIter {

  int numVertices;                   // Số đỉnh khi khởi tạo

  double[][] adjMatrix;              // Ma trận kề (given as input).

  double[][] D;                       

  public void initialize (int numVertices)

  {

    this.numVertices = numVertices;

    // Khởi tạo ma trận Dk

    D = new double [numVertices][];

    for (int i=0; i < numVertices; i++){

      D[i] = new double [numVertices];

    }

  }

  public void allPairsShortestPaths (double[][] adjMatrix)

  {

    // D = trọng số khi k = -1

    for (int i=0; i<numVertices; i++) {

      for (int j=0; j<numVertices; j++) {

        if (i != j) {

          if (adjMatrix[i][j] > 0)

            D[i][j] = adjMatrix[i][j];

          else 

            D[i][j] = Double.MAX_VALUE;

        }

        else {

          // CHÚ Ý: Chúng ta nhận D[i][j] = 0 hoặc không thể

            D[i][j] = 0;

        }

      }

    }

    // Chúng tôi sẽ dừng lại khi không có những sự thay đổi về sau

    // Bởi vậy, chúng tôi cần một biến để theo dõi whether Một Được thay đổi được xảy ra

    boolean changeOccurred = true;

    // Lặp lại không cho đến nhiều sự thay đổi hơn nào.

    while (changeOccurred) {

      changeOccurred = false;

      for (int i=0; i<numVertices; i++) {

        for (int d=0; d<numVertices; d++) {   // CHÚ Ý: "d" thay vào của"j"

          if (i != d) {

       // Cho giá trị nhỏ nhất giữa i và d, xem xét những lân cận j

            for (int j=0; j<numVertices; j++) {

              if ( (j != i) && (adjMatrix[i][j] > 0) ) {

/ / Nếu nó tốt hơn hơn j,thì quay lại giá trị mới phí mới

                if (D[j][d] + adjMatrix[i][j] < D[i][d]) {

                  D[i][d] = D[j][d] + adjMatrix[i][j];

                  changeOccurred = true;

                }

              }

            } // kết thúc end-inner-for

          } //end if

        } //end-for

      } // end-for

    } // end-while

    // Có thể viết thêm cấu trúc đường đi ngắn nhất

  }

  public static void main (String[] argv)

  {

    // Nhập trực tiếp một trường hợp cho mang A để test

      double[][] adjMatrix = {

        {0, 1, 7, 0, 5, 0, 1},

        {1, 0, 1, 0, 0, 7, 0},

        {7, 1, 0, 1, 7, 0, 0},

        {0, 0, 1, 0, 1, 0, 0},

        {5, 0, 7, 1, 0, 1, 0},

        {0, 7, 0, 0, 1, 0, 1},

        {1, 0, 0, 0, 0, 1, 0},

      };

      int n = adjMatrix.length;

      FloydWarshallIter fwAlg = new FloydWarshallIter ();

      fwAlg.initialize (n);

      fwAlg.allPairsShortestPaths (adjMatrix);

      //Có thể viết thêm để in ra đường dẫn

  }

}end programming