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

Đề tài: Bài toán tìm đường đi ngắn nhất giữa 2 đỉnh bất kỳ trong đồ thị n đỉnh

  1. #1
    Ngày gia nhập
    02 2012
    Bài viết
    4

    Mặc định Bài toán tìm đường đi ngắn nhất giữa 2 đỉnh bất kỳ trong đồ thị n đỉnh

    Mình đang học C++, mình gặp phải bài toán Tìm đường đi ngắn nhất của 2 đỉnh bất kỳ trong đồ thị n đỉnh .
    Mình chỉ dừng lại ở việc nhập vào số đỉnh, trọng số của các cạnh được nhập từ bạn phím.
    Còn phần tìm và tính khoảng cách đường đi ngắn nhất của 2 đỉnh bất kì thì mình chưa làm được.

    Bạn nào có thể giúp mình được không, mình tìm trên mạng mấy bài toán về thuật toán Deijkstra, nhưng thực sự mình không hiểu được, mà toàn chỉ có thuật toán thôi

    Mong được sự giúp đỡ của các bạn

  2. #2
    Ngày gia nhập
    02 2008
    Nơi ở
    Việt Nam
    Bài viết
    577

    Tham khảo cái này xem BFS en.wikipedia.org/wiki/Breadth-first_search
    Sample: electrofriends.com/source-codes/software-programs/cpp-programs/cpp-data-structure/c-programs-for-the-implementation-of-breadth-first-searchbfs-for-a-given-graph/

  3. #3
    Ngày gia nhập
    02 2012
    Bài viết
    4

    Đó là bài toán về cây hay sao mà bạn, có fải đồ thị n đỉnh đâu :((

  4. #4
    Ngày gia nhập
    03 2012
    Bài viết
    5

    Thuật toán này đây nè bạn
    vi.wikipedia.org/wiki/Thu%E1%BA%ADt_to%C3%A1n_Dijkstra

    Bạn cứ hình dung đơn giản ý tưởng của thuật toán thì sẽ code được thôi: ví dụ ta có 1 đường đi lần lượt qua các đỉnh A.. D...Z tạo thành đường đi ngắn nhất từ A đến Z, thì đoạn đường A...D cũng phải là đường đi ngắn nhất từ A đến D đúng không nào. Bạn cần một mảng T[][] để lưu độ dài giữa các đỉnh, T[i][j] sẽ là độ dài của đường đi ngắn nhất từ đỉnh i đến đỉnh j, khởi tạo ban đầu mảng này những đỉnh nào đi được trực tiếp với A thì gán bằng độ dài đường đi đó, nếu không thể đi trực tiếp thì gán bằng số rất lớn (coi như chưa biết ^^). Sau đó duyệt qua đồ thị, nếu thấy rằng:
    T[i][j] > T[i][z] + T[z][j] thì sẽ gán T[i][j] = T[i][z] + T[z][j] ( tức là nếu đi từ i đến j lâu hơn đi từ i đến z rồi đến j thì chọn đường đi trung gian qua z)
    Ý tưởng chính là vậy thôi, mảng trên chỉ lưu lại độ dài của đường đi, nếu muốn lưu những đỉnh cần đi qua, thì bạn phải tạo thêm 1 mảng 1 chiều để lưu vết. Sau khi đồ thị của bạn được duyệt xong, thì bạn có đường đi ngắn nhất từ A đến mọi điểm trong đồ thị chứ không riêng gì điểm Z ^^
    Đã được chỉnh sửa lần cuối bởi dnvuanh : 03-03-2012 lúc 09:29 AM.

  5. #5
    Ngày gia nhập
    02 2012
    Bài viết
    4

    @dnduyanh: Thầy giáo mình cũng nói với mình như bạn vậy, nhưng thực sự mà nói, mình cũng chỉ mới học C++, chưa thành thạo và còn rất yếu về code nên không thể hình dung được Mình hiểu thuật toán bạn nói Nhưng đọc cái code trên wiki thì chưa hiểu phải lắp vào bài của mình như thế nào Bạn có thể code cho mình được không? Có thể viết tắt công 1 vài đoạn nào bạn thấy không cần thiết để khỏi mất thời gian của bạn
    Cảm ơn

    Mình đã có mảng 2 chiều để lưu độ dài của các đường đi giữa các đỉnh rồi
    Cảm ơn bạn về câu nếu không tồn tại đường đi thì gán bằng số rất lớn Cái này giải quyết khúc mắc về cách nhập khoảng cách giữa 2 điểm mà không có đường đi

    Bạn giúp mình thêm chút nữa đi, mình sắp nghĩ ra rồi

  6. #6
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Mặc định Bài toán tìm đường đi ngắn nhất giữa 2 đỉnh bất kỳ trong đồ thị n đỉnh

    Giúp tiếp chỗ nào? Đang khúc mắc chỗ nào ?
    Nếu 2 đỉnh ko liên thông(ko có đường đi) thì gán trong ma trận kề tại vị trí đó 1 số âm cũng được, gán số lớn rồi ai biết lớn bao nhiêu mà gán.
    Um Mani Padme Hum...!!

  7. #7
    Ngày gia nhập
    03 2012
    Bài viết
    5

    Cậu post code của cậu đã viết phần nhập get dữ liệu từ file đi, rồi mọi người chỉ thêm cho, vậy cậu dễ hiểu hơn

  8. #8
    Ngày gia nhập
    02 2012
    Bài viết
    4

    C Code:
    1. #include<conio.h>
    2. #include<stdio.h>
    3. #include<stdlib.h>
    4. #include<math.h>
    5.  
    6. #define MAX 50
    7. #define TRUE 1
    8. #define FALSE 0
    9. int n,s,t;
    10. int truoc[MAX];//luu cac dinh truoc tai thoi diem dang xet cua dinh
    11. int d[MAX];//luu do dai duong di tu dinh bat dau den cac dinh con lai
    12. int DT[MAX][MAX];//do thi
    13. int cuoi[MAX];
    14. char chon;
    15.  
    16. void nhap()
    17. {
    18. int i,j;
    19. printf("So dinh cua do thi: ");
    20. scanf("%d",&n);
    21. printf("\n Ma tran khoang cach");
    22. for (i=1;i<=n;i++)
    23. {
    24. printf("\n");
    25. for(j=1;j<=n;j++)
    26. {
    27. scanf("%d",&DT[i][j]);
    28. }
    29. }
    30. }
    31.  
    32. void xuly()
    33. {
    34. int v,u,minp;
    35. printf("\n Tim duong di tu dinh s= ");
    36. scanf("%d",&s);
    37. printf(" den dinh: ");
    38. scanf("%d",&t);
    39.  
    40.  
    41.  
    42. for(v=1;v<=n;v++)
    43. {
    44. d[v]=DT[s][v];
    45. truoc[v]=s;
    46. cuoi[v]=FALSE;
    47. }
    48. truoc[s]=0;
    49. d[s]=0;
    50. cuoi[s]=TRUE;
    51. while(!cuoi[t])
    52. {
    53. minp=1000;//khoi tao do dai tu dinh dang xet den cac dinh con la 999( xap xi vo cung)
    54. for(v=1;v<=n;v++)
    55. {
    56. if((!cuoi[v])&&(minp>d[v]))//neu dodai[v] nho hon min
    57. {
    58. u=v;
    59. minp=d[v];//min bang do dai cua dodai[i]
    60. }
    61. }
    62. cuoi[u]=TRUE;
    63. if(!cuoi[t])
    64. {
    65. for(v=1;v<=n;v++)
    66. {
    67. if((!cuoi[v])&&(d[u]+DT[u][v]<d[v]))
    68. {
    69. d[v]=d[u]+DT[u][v];
    70. }
    71. }
    72. }
    73. }
    74.  
    75. }
    76. main()
    77. {
    78. int i,j;
    79. nhap();
    80. xuly();
    81.  
    82. printf("\nDuong di ngan nhat tu %d den %d la\n",s,t);
    83. printf("%d <=",i);
    84. i=truoc[i];
    85. while(i!=s)
    86. {
    87. printf("%d <= ",i);
    88. i=truoc[i];
    89. }
    90. printf("%d",s);
    91. printf("\nDo dai duong di la: %d", d[t]);
    92.  
    93.  
    94.  
    95. getch();
    96. }

  9. #9
    Ngày gia nhập
    05 2011
    Bài viết
    16

    Mô phỏng thuật toán dijkstra + code: http://y5k72pk.wordpress.com/2011/10...-nh%e1%ba%a5t/

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

  1. 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
  2. Thuật toán c# tìm đường đi ngắn nhất trong đồ thị ( toán rời rạc )
    Gửi bởi cuongcntt trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 4
    Bài viết cuối: 16-06-2011, 10:41 AM
  3. Trả lời: 0
    Bài viết cuối: 03-06-2011, 08:35 PM
  4. Lập trình C Nhập một mảng có dùng ngắt trong lập trình C?
    Gửi bởi hieu1101 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-04-2011, 10:03 PM
  5. ngắt màn hình trong C | Nhấn phím thì in chữ. XIn giúp đỡ?
    Gửi bởi van08t1 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 4
    Bài viết cuối: 03-05-2010, 04:06 PM

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