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

Đề tài: thuật toán Dijkstra lỗi general protection exception?

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

    Mặc định thuật toán Dijkstra lỗi general protection exception?

    các bạn xem giúp mình với mình viết chương trình thuật toán Dijkstra viết chương trình xong mà nó chạy cứ báo lỗi general protection exception
    chương trình của mình đây :


    #include <iostream.h>
    const MAXINT=1000;
    void main()
    {
    int a[10][10];
    int i,j,n;

    // nhap vao du lieu bai toan
    cout<<" nhap so ben ";
    cin>>n;
    for (i=1;i<=n;i++)
    for (j=1;j<=i;j++)
    {
    cout<<" \n a["<<i<<"]["<<j<<"]= ";
    cin>>a[i][j];
    }
    for (i=1;i<=n;i++)
    for (j=i+1;j<=n;j++)
    {
    a[i][j]=a[j][i];
    }
    cout<<" \n ma tran la ";
    for(i=1;i<=n;i++)

    {
    cout<<" \n ";
    for(j=1;j<=n;j++)
    {

    cout<<" a["<<i<<"]["<<j<<"]= "<<a[i][j];

    }
    }
    //thuat toan Dijjj
    int d,c;
    int *danhdau;
    int *truoc;
    int *dodai;
    int min,xp;
    danhdau= new int(n);
    truoc= new int(n);
    dodai= new int(n);
    cout<<" \n nhap diem di ";
    cin>>d;
    cout<<" \n nhap diem den ";
    cin>>c;

    // gan gia tri ban dau cho cac day
    for ( i=1;i++;i<=n )
    {
    danhdau[i]=0;

    dodai[i]=100;
    }
    danhdau[d]=1;
    truoc[d]=d;
    dodai[d]=0;
    // thuc hien while loop
    xp=d;
    while ( xp!=c )
    {
    for (i=1;i<=n;i++)
    {
    if ( (a[xp][i]>0)&&(dodai[i]> dodai[xp]+a[xp][i])&&( danhdau[i]==0 ) )
    {
    dodai[i]=dodai[xp]+a[xp][i];
    truoc[i]=xp;
    }
    }
    }
    // tim dodai ngan nhat
    min=100;
    for(i=1;i<=n;i++)
    {
    if ( min>dodai[i]&&danhdau[i]==0)
    {
    min=dodai[i];
    xp=i;
    }
    }
    danhdau[xp]=1;
    // in ra ket qua

    cout<<" \n do dai ngan nhaat la "<<dodai[c];

    cout<<" lo trinh di la ";
    while(i!=d)
    {
    i = truoc[i];
    cout<<" <- "<<i;
    }
    delete[] danhdau;
    delete[] dodai;
    delete[] truoc;
    }

  2. #2
    Ngày gia nhập
    06 2010
    Bài viết
    17

    C++ Code:
    1. #include "iostream"
    2. using namespace std;
    3. const int MAXINT=1000;
    4. void main()
    5. {
    6.     int a[10][10];
    7.     int i,j,n;
    8.  
    9.     // nhap vao du lieu bai toan
    10.     cout<<" nhap so ben ";
    11.     cin>>n;
    12.     for (i=1;i<=n;i++)
    13.     for (j=1;j<=i;j++)
    14.     {
    15.         cout<<" \n a["<<i<<"]["<<j<<"]= ";
    16.         cin>>a[i][j];
    17.     }
    18.     for (i=1;i<=n;i++)
    19.         for (j=i+1;j<=n;j++)
    20.             a[i][j]=a[j][i];
    21.     cout<<" \n ma tran la ";
    22.     for(i=1;i<=n;i++)
    23.     {
    24.         cout<<" \n ";
    25.         for(j=1;j<=n;j++)
    26.             cout<<" a["<<i<<"]["<<j<<"]= "<<a[i][j];
    27.     }
    28.     //thuat toan Dijjj
    29.     int d,c;
    30.     int *danhdau;
    31.     int *truoc;
    32.     int *dodai;
    33.     int min,xp;
    34.     danhdau= new int(n);
    35.     truoc= new int(n);
    36.     dodai= new int(n);
    37.     cout<<" \n nhap diem di ";
    38.     cin>>d;
    39.     cout<<" \n nhap diem den ";
    40.     cin>>c;
    41.  
    42.     // gan gia tri ban dau cho cac day
    43.     for ( i=1;i<=n; i++ )
    44.     {
    45.         danhdau[i]=0;
    46.         dodai[i]=100;
    47.     }
    48.     danhdau[d]=1;
    49.     truoc[d]=d;
    50.     dodai[d]=0;
    51.     // thuc hien while loop
    52.     xp=d;
    53. //Chú ý vòng while này, hai biến xp và c trong đó là không hề cho sự thay đổi trong vòng while
    54. //Vậy nên vòng này  sẽ không bao giờ kết thúc
    55.     while ( xp!=c )
    56.     {
    57.         for (i=1;i<=n;i++)
    58.         {
    59.             if ( (a[xp][i]>0)&&(dodai[i]> dodai[xp]+a[xp][i])&&( danhdau[i]==0 ) )
    60.             {
    61.                 dodai[i]=dodai[xp]+a[xp][i];
    62.                 truoc[i]=xp;
    63.             }
    64.         }
    65.     }
    66.     // tim dodai ngan nhat
    67.     min=100;
    68.     for(i=1;i<=n;i++)
    69.     {
    70.         if ( min>dodai[i]&&danhdau[i]==0)
    71.         {
    72.             min=dodai[i];
    73.             xp=i;
    74.         }
    75.     }
    76.     danhdau[xp]=1;
    77.     // in ra ket qua
    78.  
    79.     cout<<" \n do dai ngan nhaat la "<<dodai[c];
    80.  
    81.     cout<<" lo trinh di la ";
    82.     while(i!=d)
    83.     {
    84.         i = truoc[i];
    85.         cout<<" <- "<<i;
    86.     }
    87.     delete[] danhdau;
    88.     delete[] dodai;
    89.     delete[] truoc;
    90. }

    Mình giải thích ở trên đó, tại mình thực mới đọc qua nên chưa hiểu rõ chương trình làm gì, nhưng đọc đến vòng while đó mình thấy lỗi.
    Chúc bạn thành công!
    PS: Cậu là lập trình viên, nên cậu chú ý viết code sao cho dễ đọc
    C++ Code:
    1. int i=0, n=1;
    2. while(i<n)
    3.     cout << "Vô tận!";

  3. #3
    Ngày gia nhập
    07 2011
    Bài viết
    160

    Cho cái đoạn giữa 2 comment "tìm độ dài ngắn nhất" và "in ra kết quả" vào cuối vòng while mà duchieu nói đó
    Thực tế đoạn đó là "tìm đỉnh có độ dài đường đến đó ngắn nhất, mà chưa được đánh dấu"
    Với cả khởi tạo min = 100 có bé quá không nhỉ? Sao không gán bằng hẳn 1 triệu, 1 tỷ đi )

    Vài lỗi và điểm chưa hợp lý khác: (lỗi tùm lum)
    - Mảng trong C/C++ bắt đầu từ 0. Nếu muốn dùng từ 1->n cũng được nhưng phải cấp phát cho n+1 phần tử
    - Nhập dữ liệu cả cho a[i][i] ==> không cần thiết. Chỉ cần for j đến i-1
    - Lúc lần ngược để in ra bắt đầu từ i, mà i là biến for (lúc đó nó sẽ có giá trị n+1). Đáng lẽ phải bắt đầu từ c hoặc xp
    - Lộ trình in ra không bao gồm điểm cuối
    - Tên thuật toán là dijkstra chứ không phải đi ị (dijjj) ^^
    - C++ không cho phép main trả về void (có thể trình dịch của bạn không báo lỗi hoặc chỉ báo warning - nhưng sai là sai)
    - Chưa xét đến trường hợp đầu và cuối không liên thông (thấy code có kiểm tra a[xp][i] > 0 nên mình coi trường hợp <= 0 là không có cạnh). Gặp trường hợp này (đến 1 đỉnh xp nào đó mà tất cả các đỉnh i chưa đánh dấu đều có a[xp][i] <= 0) sẽ lặp vô hạn
    - a[10][10] ==> Hỗ trợ tối đa 10 đỉnh. Có 10 đỉnh mà mấy mảng 1 chiều danhdau, dodai, truoc cũng phải cấp phát động cho mắc công =)). Còn trường hợp n lớn thì mảng 2 chiều a là cái đầu tiên cần cấp phát động

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

    Các bạn giúp mình sửa lại bài được không? mình đã cho đoạn tìm min vào trong vòng lặp while rồi mà vẫn không được, hic!

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

  1. Lập trình C các bạn cho tớ gợi ý về bài toán sau với :ứng dụng hàng đợi có ưu tiên vào cài đặt thuật toán dijkstra
    Gửi bởi vu thien phuong trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 0
    Bài viết cuối: 03-09-2012, 05:32 PM
  2. Xin code thuật toán dijkstra viết bằng C#
    Gửi bởi duonggadget trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 1
    Bài viết cuối: 07-03-2012, 08:22 PM
  3. thuật toán dijkstra cho tìm đường đi ngắn nhất?
    Gửi bởi tuanvu_n trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 24-11-2010, 01:40 AM
  4. vì sao thuật toán Dijkstra không áp dụng cho đồ thị có trọng số âm?
    Gửi bởi changyng 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: 03-11-2010, 10:10 PM
  5. Lỗi General Protection Exception
    Gửi bởi svcntt trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 5
    Bài viết cuối: 14-09-2010, 12:50 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