Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội

Chia sẻ kiến thức mọi mặt của các lớp cao học CNTT, Học viện Kỹ thuật Quân sự




Chào mừng đã đến với forum khmt.123.st
  • Bạn chưa đăng kí (hoặc chưa đăng nhập) nên quyền lợi của bạn sẽ bị hạn chế. Việc đăng kí làm thành viên hoàn toàn miễn phí, sau khi đăngkí bạn có thể post bài, tham gia thảo luận , nhìn thấy link ở những box hạn chế ... và rất nhiều quyền lợi khác. Thủ tục đăng kí rất nhanh chóng và đơn giản, hãy Đăng kí làm thành viên !
  • Nếu bạn quên mật khẩu, xin nhấn vào đây !
  • Nếu bạn gặp trục trặc trong vấn đề đăng kí hoặc không thể đăng nhập, hãy liên hệ với chúng tôi.




  • Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down  Thông điệp [Trang 1 trong tổng số 1 trang]

    Admin


    Quản trị viên
    Quản trị viên
    Đường đi ngắn nhất giữa 2 đỉnh trên đồ thị có trọng số cho bởi ma trận trọng số, n cạnh.
    Bài này chỉ xét liên thông, nếu xét không liên thông phải thêm điều kiện.

    Biến sử dụng:

    - Ma trận A (i, j) là ma trận trọng số.
    - Đỉnh u (io, jo). Đỉnh v(iv, jv).
    - λ(x): Khoảng cách ngắn nhất từ đỉnh u đến đỉnh x.
    - S(x): Mảng đánh dấu đỉnh. Nếu x Э S, giá trị S(x) = 1, ngược lại S(x) = 0.

    A) Khởi tạo
    1) //Đưa tất cả các khoảng cách đỉnh với đỉnh xuất phát u = ∞ và đánh dấu các đỉnh này là 0. Tập lưu trữ các đỉnh này là rỗng, tương ứng với giá trị S(đỉnh) = 0;
    FOR i = 1 TO n DO
    a) λ(i) = ∞;
    b) S(i) = 0;
    2) //Đặt khoảng cách cho đỉnh xuất phát là 0, đỉnh xuất phát là u
    a) λ(u) = 0;
    b) stop := false;

    B) Dán nhãn các đỉnh
    WHILE (S(v) ≠ 0) & !Stop DO
    1)
    a) a = v;
    b) FOR x := 1 TO n DO
    IF (S(x) = 0) & (λ(x) < λ(a)) THEN a := x;
    c) IF λ(a) < ∞ THEN S(a) := 1;
    ELSE Stop := True;
    2) IF Stop = true THEN
    FOR (λ(a) < ∞) & (λ(x) > λ(a) + D(a, j)) THEN λ(x) = λ(a) + D(a, x);

    C) Chỉ định đường đi
    IF !Stop THEN
    1) k = j; C(k) = v;
    2) WHILE C(k) ≠ u DO
    a) x := 1;
    WHILE !(D(x, C(k)) < ∞ & λ(C(k) = λ(x) + D(x, C(k))) DO x++;
    b) C(k+1) = x; k++;

    D)IF (!Stop) THEN Output λ(v), C(k); C(k-1)...C(1);
    ELSE Output "Đồ thị không liên thông"



    Được sửa bởi Admin ngày Sat Aug 13, 2011 6:45 pm; sửa lần 3.


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    hungbeo_fm2008


    Chuyên viên
    Chuyên viên
    Hình như anh làm nhầm rồi thì phải. Đây là ma trận trọng số chứ có phải là ma trận kề đâu mà anh dùng D(a,i)
    Phải viết một function F (x,y: tên đỉnh): giá trị;
    - nếu x,y thuộc E thì F:= D(i).t
    ELSE F:= +vô cùng;
    Khi đó sẽ có điều kiện:
    If F(a,i) and lamda(i) = +vô cùng THEN

    .........

    (xin lỗi vì em lười chèn kí tự nên đành viết tiếng việt :D)

    Admin: Bài trên là bài thầy chữa hôm thứ 3 ngày 26/7/2011 tại phòng giao ban Khoa CNTT, lớp mình đi học ở đó. Còn nếu thấy sai thì nên ý kiến với thầy, anh chỉ gõ lại cho những người vắng tham khảo thôi.


    ================
    Phong độ là nhất thời, đẳng cấp mới là mãi mãi. [You must be registered and logged in to see this image.]

    Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang  Thông điệp [Trang 1 trong tổng số 1 trang]

    Permissions in this forum:
    Bạn không có quyền trả lời bài viết

     

    Ghi rõ nguồn khi copy các bài viết từ Website này.
    Bản quyền thuộc Khoa học Máy tính. Số lượt truy cập tính đến hiện tại:Website counter
    Modified skin by Nguyễn Anh Cường. Developed by Members of http://khmt.123.st

    Free forum | © PunBB | Free forum support | Liên hệ | Report an abuse | Create a free blog