Từ 1 tới 2 trên tổng số 2 kết quả

Đề tài: bài toán tìm đường đi ngắn nhất

  1. #1
    Ngày gia nhập
    04 2009
    Bài viết
    7

    Mặc định bài toán tìm đường đi ngắn nhất

    mình có đoạn code tìm đường đi ngắn nhất giữa mọi cặp đỉnh của đồ thị viết theo Floyd như sau:
    C Code:
    1. #include <stdio.h>
    2. #include <conio.h>
    3.  
    4. #define TOIDA 50
    5. #define VOCUNG 30000
    6. #define TRUE 1
    7. #define FALSE 0
    8.  
    9. /* Khai bao ma tran trong so cua do thi
    10.     weight[i][j] =  0    : neu i = j
    11.     weight[i][j] =  VOCUNG: neu tren do thi khong co cung <i, j>
    12.     weight[i][j] != 0    : tren do thi co cung <i, j> */
    13. int weight[TOIDA][TOIDA];
    14.  
    15. /* Ma tran D[][]: ma tran cho biet chieu dai ngan nhat di tu nut x den
    16.   nut y */
    17. int D[TOIDA][TOIDA];
    18.  
    19. /* Ma tran P[][]: ma tran cho biet duong di ngan nhat tu nut x den nut y co
    20.   qua nut trung gian P[x][y] hay khong:
    21.       * Neu P[x][y] == -1: duong di ngan nhat tu nut x den nut y khong
    22.         qua nut trung gian
    23.       * Neu P[x][y] != -1: duong di ngan nhat tu nut x den nut y co di
    24.         qua nut trung gian P[x][y]. */
    25. int P[TOIDA][TOIDA];
    26.  
    27. int SoNut;
    28.  
    29. // Khoi dong ma tran trong so cua do thi
    30. void initialize()
    31. {
    32.     int i, j;
    33.     for(i = 0; i < TOIDA; i++)
    34.         for(j = 0; j < TOIDA; j++)
    35.         if(i == j)
    36.             weight[i][j] = 0;
    37.         else
    38.               weight[i][j] = VOCUNG;
    39. }
    40. void floyd()
    41. {
    42.     int i, j, k;
    43.  
    44.     // Khoi dong ma tran D va P
    45.     for(i = 0; i < SoNut; i++)
    46.         for(j = 0; j < SoNut; j++)
    47.         {
    48.             D[i][j] = weight[i][j];
    49.             P[i][j] = -1;
    50.         }
    51.  
    52.     // Tinh ma tran D va P o buoc lap thu k
    53.     for(k = 0; k < SoNut; k++)
    54.         for(i = 0; i < SoNut; i++)
    55.             if((D[i][k] > 0) && (D[i][k] < VOCUNG))
    56.                 for(j = 0; j < SoNut; j++)
    57.                     if((D[k][j] > 0) && (D[k][j] < VOCUNG))
    58.                         if(D[i][j] != 0 && D[i][k]+D[k][j] < D[i][j])
    59.                         {
    60.                             D[i][j] = D[i][k]+D[k][j];
    61.                             P[i][j] = k;
    62.                         }
    63. }
    64.  
    65. // In lo trinh ngan nhat
    66. void inlotrinh(int x, int y)
    67. {
    68.     int r;
    69.     if(P[x][y] == -1)
    70.     {
    71.         printf(" %d -> %d ", x, y);
    72.         return;
    73.     }
    74.     else
    75.     {
    76.         r = P[x][y];
    77.         inlotrinh(x, r);
    78.         inlotrinh(r, y);
    79.     }
    80. }
    81.  
    82. // Chuong trinh chinh
    83. void main()
    84. {
    85.     int i, j, chucnang, x, y, trongso;
    86.     char c;
    87.     int p, q, r;
    88.     clrscr();
    89.  
    90.     initialize();  // Khoi dong do thi
    91.   SoNut = 0;
    92.  
    93.     do
    94.     {
    95.         // menu chinh cua chuong trinh
    96.         printf("\n\n\t\tGRAPH - GIAI THUAT FLOYD TIM DUONG DI NGAN NHAT");
    97.         printf("\n\nCac chuc nang cua chuong trinh:\n");
    98.         printf("  1: Tao do thi moi\n");
    99.         printf(2 : Tao do thi moi bang cach nhap ngau nhien \n “);
    100.         printf("  3: Them mot nut\n");
    101.         printf("  4: Them mot cung\n");
    102.         printf("  5: Xoa mot cung\n");
    103.         printf("  6: Xoa toan bo do thi\n");
    104.         printf("  7: Xac dinh so nut co tren do thi\n");
    105.         printf("  8: Duyet cac cung\n");
    106.             printf("  9: Tim cung\n");
    107.         printf("  10: Tim duong di ngan nhat (giai thuat Floyd)\n");
    108.         printf("  0: Ket thuc chuong trinh\n");
    109.         printf("Chuc nang ban chon: ");
    110.         scanf("%d", &chucnang);
    111.         switch(chucnang)
    112.         {
    113.             case 1:
    114.             {
    115.                 initialize();
    116.             SoNut = 0;
    117.                 printf("\nDo thi moi co bao nhieu nut: ");
    118.                 scanf("%d", &SoNut);
    119.                 printf("\Hay nhap cac cung cua do thi (nhap %d %d de ket thuc):\n",
    120.                         SoNut, SoNut);
    121.                 x = 0;
    122.                 y = 0;
    123.                 while(x < SoNut && y < SoNut)
    124.                 {
    125.                     printf("  Nhap cung: ");
    126.                     scanf("%d %d", &x, &y);
    127.                     if(x < SoNut && y < SoNut)
    128.                     {
    129.                         printf("  Trong so cua cung %d %d: ", x, y);
    130.                         scanf("%d", &trongso);
    131.                         joinwt(x, y, trongso);
    132.                     }
    133.                 };
    134.                 break;
    135.             }
    bài toán này dc biểu diễn bởi ma trận trọng số.mình mới chỉ code dc cách nhập từ bàn phím nhưng gặp phải vấn đề nều đồ thị cho là 400 đỉnh chằng hạn( đò thj là có hướng) thì với cách nhập bằng bàn phím như nhập cung và trọng số cho cả 400 đỉnh chắc là mỏi tay.mình chưa biết cách lưu trữ tn cho phù hợp và tạo dc dữ liệu với đồ thị nhiều đỉnh 1 cách nhanh và dễ dàng.mình chưa biết cách xử lí vấn đề này ra sao.mong các bạn giúp đỡ

  2. #2
    Ngày gia nhập
    09 2009
    Bài viết
    2

    Bạn có thể dùng tệp mà.Ah bạn co code C# bài này không cho mình xin

Các đề tài tương tự

  1. Lập trình C Hàm tạo số ngẫu nhiên | Cách nhập giá trị ngẫu nhiên cho ma trận?
    Gửi bởi chuong01 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 15
    Bài viết cuối: 13-08-2012, 09:43 PM
  2. Tim từ ngắn nhất và dài nhất trong chuổi lỗi has stopped working?
    Gửi bởi satthuprao trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 3
    Bài viết cuối: 27-05-2012, 11:51 AM
  3. Trả lời: 0
    Bài viết cuối: 03-06-2011, 08:35 PM
  4. Thảo luận về thuật toán tìm đường đi ngắn nhất (có chi phí ít nhất) trên ma trận
    Gửi bởi hunterphu trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 10
    Bài viết cuối: 10-08-2010, 12:05 AM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn