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();
}

Đừ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!!

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.

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ứ"

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

@[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.]

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 :-)

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.

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

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