Đạ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]

    vitaminC2009

    vitaminC2009
    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Mình có 1 đoạn code tìm đường đi ngắn nhất bằng Dijkstra, nhưng muốn tìm đường đi dài nhất phải thế nào đây hic hic
    Đoạn code tìm đường đi ngắn nhất như sau :-(
    #include
    #include
    #include
    #include
    #define FileIn "Bai7.inp"

    void Doc_File(int**A, int &n, int &D, int &C){
    FILE*f = fopen("I:\\Bai7.inp","rb");
    fscanf(f,"%d%d%d",&n,&D,&C);
    cout<<"Ma Tran Lien Ket Tuong Ung.\n"< *A = new int [n];
    FOR(int i =0;i A[i] = new int [n];
    FOR(int j =0;j fscanf(f,"%d",&A[i][j]);
    cout< }
    cout< }
    fclose(f);
    D--; C--;
    }

    void Dijkstra(int **A, int n, int D, int C) {
    char *DanhDau = new char[n];
    int *Nhan = new int[n];
    int *Truoc = new int[n];
    int XP, min;
    FOR(int i=0; i Nhan[i] = MAXINT;
    DanhDau[i] = 0;
    Truoc[i] = D;
    }
    Nhan[D] = 0;
    DanhDau[D] = 1;
    XP = D;
    WHILE(XP != C){
    FOR(int j=0; j if(A[XP][j]>0 && Nhan[j]>A[XP][j]+Nhan[XP] && DanhDau[j]==0) {
    Nhan[j] = A[XP][j]+Nhan[XP];
    Truoc[j] = XP;
    }
    min = MAXINT;
    FOR(j = 0; j if(min>Nhan[j]&& DanhDau[j]==0){
    min = Nhan[j] ;
    XP = j ;
    }
    DanhDau[XP] = 1;
    }
    cout<<"Duong Di Ngan Nhat La:"< cout< i = Truoc[C];
    WHILE(i!=D){
    i = Truoc[i];
    cout<<" <- "< }
    } void main() {
    int**A,n,Dau,Cuoi;
    Doc_File(A,n,Dau,Cuoi);
    Dijkstra(A,n,Dau,Cuoi);
    delete*A;
    getch();
    }

    dlvt2003

    dlvt2003
    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Đừng bao giờ nghĩ đến điều này em nha!! Nguyên nhân: "Đường càng đi càng xa".
    Em có thể suy nghĩ các cách khác như: FordBellman, TopoSorting, Recursive & DynamicProgramming and Approximate...
    Ngoài ra cũng nên dùng Tarjan Algorithm để test chu trình cho dữ liệu đầu vào!!
    Thế là quá đủ cho 1 đồ án môn học cho em!! Còn nếu muốn nghiên cứu sâu hơn nữa thì vào Google nha!!

    vitaminC2009

    vitaminC2009
    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    dlvt2003 đã viết:Đừng bao giờ nghĩ đến điều này em nha!! Nguyên nhân: "Đường càng đi càng xa".
    Em có thể suy nghĩ các cách khác như: FordBellman, TopoSorting, Recursive & DynamicProgramming and Approximate...
    Ngoài ra cũng nên dùng Tarjan Algorithm để test chu trình cho dữ liệu đầu vào!!
    Thế là quá đủ cho 1 đồ án môn học cho em!! Còn nếu muốn nghiên cứu sâu hơn nữa thì vào Google nha!!
    Thanks a đã quan tâm topic của em. Thật ra thì cũng không phải đường càng đi càng xa đâu anh. Vì đồ thị của em áp dụng là đồ thị có hướng và không có chu trình mà. Nghĩa là sẽ bắt đầu đi từ node nguồn và mọi nhánh sẽ kết thúc tại một node đích.

    Admin

    Admin
    Quản trị viên
    Quản trị viên
    Có hẳn một đống code về vấn đề này trong mục Kho bài chuẩn. Những bạn nào cần đao thì phải đăng ký đầy đủ tên và họ thật và tham gia "Thành viên đọc được mọi thứ"

    https://khmt.123.st

    trungttnd

    trungttnd
    Thành viên cao cấp
    Thành viên cao cấp
    dùng cách thô nhất là vét cạn để tìm ra đường đi dài nhất là đc

    dlvt2003

    dlvt2003
    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    @[You must be registered and logged in to see this link.]
    Em chưa hiểu ý câu đấy của anh rồi!! Có lẽ em nên liên hệ với anh Admin để xin mấy bài các anh vừa làm xong về xem thế nào nha!!
    Nếu không thể có thể đưa mail anh send cho báo cáo của anh để em đọc rõ hơn vấn đề này !! oka!
    [You must be registered and logged in to see this link.]

    vitaminC2009

    vitaminC2009
    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    dlvt2003 đã viết:@[You must be registered and logged in to see this link.]
    Em chưa hiểu ý câu đấy của anh rồi!! Có lẽ em nên liên hệ với anh Admin để xin mấy bài các anh vừa làm xong về xem thế nào nha!!
    Nếu không thể có thể đưa mail anh send cho báo cáo của anh để em đọc rõ hơn vấn đề này !! oka!
    [You must be registered and logged in to see this link.]
    Em có tìm trên google và có một số bài viết chỉ nói là đổi dấu trọng số và 1 vài điều kiện trong chương trinh thì sẽ được chiều dài dài nhất, nhưng bài viết chỉ nói đại khái thế thôi, em có chỉnh sửa đoạn chương trinh lại và vẫn không ra có lẽ làm không đúng cách nên đành chịu. Anh send qua đó giúp e nhé, thanks a nhìu nhìu :-) (ChamChi)



    Được sửa bởi vitaminC2009 ngày Mon Dec 03, 2012 11:08 pm; sửa lần 2.

    vitaminC2009

    vitaminC2009
    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Admin đã viết:Có hẳn một đống code về vấn đề này trong mục Kho bài chuẩn. Những bạn nào cần đao thì phải đăng ký đầy đủ tên và họ thật và tham gia "Thành viên đọc được mọi thứ"
    Em có edit lại thông tin của mình rồi, anh check lại giùm e xem đã oki chưa nhé. Thanks anh nhìu.

    seagull

    seagull
    Thành viên ít chịu khó
    Thành viên ít chịu khó
    Có ai biết biết thuật toán vét cạn tìm đường đi dài nhất không (code C++ nhé)
    Cần gấp
    Thanks all

    vitaminC2009

    vitaminC2009
    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Cái này đơn giản thôi, tìm thuật toán vét cạn tìm đường đi ngắn nhất rồi đổi dấu 1 số điều kiện so sánh, (theo như mình đã tìm đường đi dài nhất ở bellman hay floyd thì mình đảo dấu trọng số, thằng dijsktra thì ko đảo dấu đc nên chịu :D). Còn 1 điều nữa phải xem xét đó là đường đi dài nhất thì phải là đồ thị có hướng và không có chu trình nhe

    Sponsored content


    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 https://khmt.123.st

    Free forum | ©phpBB | Free forum support | Báo cáo lạm dụng | Thảo luận mới nhất