About me

Thành Viên

Thống kê

Unknown AuthorTác giả: dangvinh | Date21:13 Date
Thuật toán được mô ta như sau:

Mỗi đỉnh i sẽ được gán 2 nhãn:
Nhãn thứ nhất là Check[i]. Check[i]=0 nếu D[i] còn có thể tối ưu được.
Check[i]=1 nếu D[i] không thể tối ưu được nữa.
Nhãn thứ hai là giá trị D[i].

Bài toán cài đặt bằng pascal
Procedure DD
Begin
  Với mọi k, D[k]=VC, Check[k]=0, Trace[k]=k;
  D[s]=0;
  dung=false
  repeat
    tìm m có Check[m]=0 và D[m] nhỏ nhất
    Chech[m]=1;
    Với các đỉnh v kề với m có Check[m]=0,
            nếu D[v] < D[m] + a[m,v] thì
      gán lại D[v]=D[m] + a[m,v];
      trace[v]=m;
  until dung;
end

Trên đây chỉ là thuật toán, nếu các bạn hiểu và áp dụng thì ok, còn nếu chưa nắm rõ thì cứ liên lạc dangvinh, dangvinh sẽ gửi cách giải thích và ví dụ minh họa trực quan các bạn sẽ kịp thời nắm bắt liền.

Chúc các bạn ứng dụng tốt thuật toán này !
Submit link to Hay!   

Chia sẻ lên zing
Hãy chia sẻ những bài viết hay đến bạn bèngười thân.
Tags:
truelovewait Email
2013/05/30 06:53
Cho đồ thị N đỉnh, M cạnh một chiều u->v có độ dài L và chí phí là V. (L, V>0). + Tìm đường đi ngắn nhất từ S->T sao cho tổng chi phí trên đường đi lớn hơn K (K là số cho trước) Thầy có thể hướng dẫn cho em làm bài này không ạ
nlong96 Email
2013/05/24 00:10
Anh ơi cho em hỏi tại sao tất cả các chu trình trong đồ thị có độ dài đường thì đường đi ngắn nhất từ 1 đỉnh tới 1  đỉnh trong đồ thị không bị trùng lặp đỉnh
thanhhuyen Email
2012/02/07 07:58
Ý anh là đổi dấu trong điều kiện sao. Anh code bằng C giúp e với.Thanks anh.
dangvinh Email
2012/02/06 10:43
Em vẫn dùng thuật toán Dijkstra để giải quyết bài toán trên, nhưng phải thay đổi một chút trong điều kiện và cách đánh giá đường đi dài nhất đó.
thanhhuyen Email
2012/02/06 09:20
Là tìm đường đi dài nhất mà anh.
dangvinh Email
2012/02/05 22:27
Tìm đường đi ngắn nhất hay dài nhất vậy em
thanhhuyen Email
2012/02/05 18:54
Chào anh!
Em muốn hỏi anh một bài tập như sau: tìm đường đi dài nhất trong đồ thị có trọng số dương,đồ thị có hướng.Theo anh thì nên sử dụng thuật toán nào cho bài tập này. Không biết cách đổi trọng số của đồ thị rồi áp dụng thuật toán Bellman-Ford có được không? Mong phản hồi sớm của anh. Cám ơn anh nhiều.
datauday92 Email
2011/12/09 01:14
help Me!!!!!!!!!!!!!!!!!!!!!. mung 10 la phai nop roi anh oi giup em voi:(:(
datauday92
2011/12/07 23:34
cam on anh rat nhiu ak:D.
anh oi cai phan
Tiến hành thực nghiệm, để đưa ra nhận xét đánh giá các thuật toán
em khong bit lam ntn ak:(. vi chua lam bh, voi lai em cung khong hieu ntn nua
voi lai thay em bat cai dat bang dev C ak:(
"2)  Ngôn ngữ lập trình: C, C++. Sử dụng bộ dịch: DEVCPP. Không được sử dụng thư viện của bộ dịch cung cấp sẵn về ADT mà đề tài yêu cầu cài đặt!"
dangvinh Email
2011/12/07 10:16
Tạm thời em tham khảo chương trình tìm đường đi ngắn nhất này nhé.
Có Source code cho em luôn đó.

http://www.mediafire.com/?g51hmsmh5pivwcr
Chúc em báo cáo tốt.
Phân trang 1/2 Trang đầu 1 2 Trang sau Trang cuối
Viết nhận xét
  Tên gọi [Đăng ký]
  Mật khẩu (Khách không cần mật khẩu)
  Địa chỉ web
  Email
OpenID登入 权限选项 Hình vui