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

Đề tài: Thuật toán cải tiến Dijkstra tìm tất cả đường đi ngắn nhất từ a đến b

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

    Exclamation Thuật toán cải tiến Dijkstra tìm tất cả đường đi ngắn nhất từ a đến b

    như title em code xong Dijkstra nhưng chỉ in được 1 đường từ a->b thui , làm sao để in ra tất cả đường đi ngắn nhất từ a đến b..

  2. #2
    Ngày gia nhập
    09 2009
    Nơi ở
    Hoa sơn tuyệt đỉnh
    Bài viết
    407

    DIJK từ a ta có mảng d
    BFS ngược lại từ b
    Push b vào hàng đợi, lấy đỉnh u từ hàng đợi, từ u có đường đi đến v nếu d[v]+c[v][u]=d[u] thì v là 1 đỉnh thỏa
    Mình nghĩ bài này chỉ nên đếm số đường đi ngắn nhất, chứ in ra hết thì .....

    my houses
    my school
    tỐnG lÊ cHâN mAnG kỶ nIệM bUồN cHo AnH...

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

    Trích dẫn Nguyên bản được gửi bởi hunterphu Xem bài viết
    DIJK từ a ta có mảng d
    BFS ngược lại từ b
    Push b vào hàng đợi, lấy đỉnh u từ hàng đợi, từ u có đường đi đến v nếu d[v]+c[v][u]=d[u] thì v là 1 đỉnh thỏa
    Mình nghĩ bài này chỉ nên đếm số đường đi ngắn nhất, chứ in ra hết thì .....
    Đề yêu cầu là mở rộng thuật toán DIJK không biết có cách khác không...
    Đã được chỉnh sửa lần cuối bởi huutho444 : 25-10-2011 lúc 09:02 PM. Lý do: Viết thiếu
    Cố gắng và chỉ biết cố gắng mà thôi....

  4. #4
    Ngày gia nhập
    08 2009
    Bài viết
    6

    Mặc định Dijkstra có thể tìm đường ngắn nhất từ a -> mọi đỉnh

    Thuật toán Dijkstra có thể áp dụng để tìm kiếm đường đi ngắn nhất từ 1 đỉnh đến tất cả các đỉnh còn lại trong đồ thị.
    Theo như bạn mô tả thì chỉ có thể tìm được đường đi từ a -> b thì mình nghĩ trong lúc tìm đường, bạn kiểm tra nếu đỉnh tối ưu (min cost) là b thì thoát luôn.
    Nếu muốn tìm đường đi từ a -> mọi đỉnh thì đừng kiểm tra đã tới đích hay chưa mà chỉ dừng tìm kiếm khi thỏa mãn 1 trong 2 điều kiện:
    1. Đã tìm hết tất cả đường đi từ a -> các đỉnh khác
    2. Đỉnh tối ưu đang xét là đỉnh không thể tới được từ a (min cost = INFINITY)

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

    mình nghĩ thế này..khi bạn dùng dijsktra thì bạn k nên dừng lại ở chỗ mà if((u==0)||(u==b) mà bạn nên dừng lại chỉ khi (u==0) thôi...khi đó bạn đã biết chi phí đi từ a-->b. rồi lúc đó bạn duyệt tất cả các đỉnh mà T[u]+a[u][b]==chi phí thì bạn in ra..

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

  1. thuật toán tìm đường đi ngắn nhất(dijkstra)
    Gửi bởi shogun_vn trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 7
    Bài viết cuối: 04-11-2015, 06:14 PM
  2. Thuật toán Dijkstra và bài toán tìm đường đi ngắn nhất giữa các đỉnh trong đồ thị
    Gửi bởi Cloud Strife trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 22
    Bài viết cuối: 12-09-2014, 05:12 PM
  3. Tìm đường đi ngắn nhất bằng giải thuật dijkstra trong lập trình C
    Gửi bởi minhtoan991 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 0
    Bài viết cuối: 25-02-2011, 12:26 PM
  4. 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
  5. Tỉm đường đi ngắn nhất bằng giải thuật Dijkstra
    Gửi bởi thnam35 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: 13-03-2010, 11:11 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