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

Đề tài: Làm thế nào để xuất đường đi ngắn nhất dùng Floyd?

  1. #1
    Ngày gia nhập
    05 2008
    Bài viết
    24

    Mặc định Làm thế nào để xuất đường đi ngắn nhất dùng Floyd?

    Code:
    void floyd()
    {
       int i,j,k,p[max][max];
    	for(k=0;k<n;k++)
       	     for(i=0;i<n;i++)
          	        for(j=0;j<n;j++)
             	     if((A[i][k]!=inf)&&(A[i][k]+A[k][j]<A[i][j]))
                	         A[i][j]=A[i][k]+A[k][j];
       
    }
    thuật toán tìm chỉ có như vậy thôi. Nhưng làm sao để xuất được. Ví dụ như:
    mảng ma trận giá như thế này
    0 27 16
    14 0 65535
    65535 10 0
    //vô cùng=inf=65535
    Mảng A sau khi Floyd là
    0 26 16
    14 0 30
    24 10 0
    Đi từ 2->3 độ dài nhỏ nhất là 30. Làm thế nào để xuất được đường đi ngắn nhất là 2->1->3

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

    cho bạn đoạn code của mình

    C Code:
    1.  
    2.  
    3. void PrintScreen(int iStart)
    4. {
    5.     int iEnd;
    6.     for(int j=0; j<nSize; j++)
    7.     {
    8.         if(pCost[iStart][j]>0 && iStart!=j)
    9.         {
    10.             iEnd = j;
    11.            
    12.             printf("\n Chi phi di tu dinh %d--->%d la:%d\n",iStart,iEnd,pCost[iStart][iEnd]);
    13.             printf(" Voi chu trinh:\n");
    14.  
    15.             int k = prevNode[iStart][iEnd];
    16.             printf("%d->%d",iStart,k);
    17.             while(k != iEnd)
    18.             {
    19.                 //printf("->%4d",k);
    20.                 k = prevNode[k][iEnd];
    21.                 printf("->%d",k);
    22.             }
    23.         }
    24.         printf("\n");
    25.     }
    26. }

    Bạn xem thử, không hiểu chổ nào post lên mình giải thích cho.

  3. #3
    Ngày gia nhập
    05 2008
    Bài viết
    24

    int k = prevNode[iStart][iEnd]
    mảng prevNode có giá trị đầu là gì vậy bạn.

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

    à mình quên mất

    đây là code khởi tạo của nó.
    C++ Code:
    1. for(int l=0; l<g.GetN(); l++)
    2.     {
    3.         for(int k=0; k<g.GetN(); k++)
    4.         {
    5.             if(pCost[l][k]> 0)
    6.                 prevNode[l][k] = k; // nếu mà có đường đi từ l->k thì nó lưu lại thằng ở sau là k
    7.             else
    8.                 prevNode[l][k] = -1; // không thì lưu -1.
    9.         }
    10.     }

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

  1. Bài tập C++ bài toán tìm đừong đi ngắn nhất bằng thuật toán FLoyd , đoạn code C++ bị lỗi các bạn xem giúp mình
    Gửi bởi BornIsBAD trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 30-11-2012, 09:23 AM
  2. Lý thuyết giải thuật Thuật giải tìm đường đi ngắn nhất tửng đỉnh xuất phát qua tất cả các đỉnh và quay về chính nó như thế nào?
    Gửi bởi kitti trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 0
    Bài viết cuối: 13-11-2012, 07:52 PM
  3. Bài tập C++ Nhập 1 số n kiểu long( dùng ngắt 0X21), rồi đổi n ra xâu ký tự thập phân TP char *s?
    Gửi bởi nicky2222 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: 04-05-2012, 03:06 PM
  4. Nhập 1 số n kiểu long (dùng ngắt 0X21), rồi đổi n ra xâu ký tự thập phân TP char *s
    Gửi bởi hklong trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 2
    Bài viết cuối: 01-03-2012, 04:47 PM
  5. giải thuật Floyd tìm đường đi ngắn nhất
    Gửi bởi nguoikhonglo171 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 0
    Bài viết cuối: 25-03-2011, 11:40 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