DIỄN ĐÀN ĐÀ NẴNG - DANANG FORUM

DIỄN ĐÀN ĐÀ NẴNG - DANANG FORUM (http://forum.dng.vn/index.php)
-   C/C++ (http://forum.dng.vn/forumdisplay.php?f=343)
-   -   C++: Thuật toán DIJKSTRA tìm đường đi ngắn nhất (http://forum.dng.vn/showthread.php?t=11249)

megaboy_dn 25-06-2010 10:14 PM

C++: Thuật toán DIJKSTRA tìm đường đi ngắn nhất
 
Mới biết được code tìm đường nên post lên chia sẻ, hy vọng nó có ích trong một số trường hợp:

Gồm 1 file source và một file input (g9.cpp)

Trích:

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
#include<stdio.h>
#define MAXINT 0x7FFF
int a[20][20],w[20][20],n,m;
int dd[20];
int min(int a, int b)
{
if(a<b) return a; else return b;
}
void docdlts()
{
FILE *f;
int i,j;
f=fopen("g9.cpp","rt");
if(f==NULL) cout<<"ko mo duoc file!";
else
{
int d,c,k;
fscanf(f,"%d%d",&n,&m);
for(i=1; i<=n; i++)
for(j=1; j<=n; j++) w[i][j]=MAXINT;
for(i=1; i<=m; i++)
{
fscanf(f,"%d%d%d", &d,&c,&k);
w[d][c]=w[c][d]=k;
}
cout<<"\n da doc xong file du lieu!";
fclose(f);
getch();
}
}
void dijkstra(int a, int z)
{
int i,j,v,x;
int L[100],T[100], HT[100]; //L nhan cac dinh,
// T la tap cac dinh
// HT : mang luu duong di tu a-->z
//buoc 1: Khoi gan
for(x=1; x<=n; x++) L[x]=MAXINT;
L[a]=0;
for(x=1; x<=n; x++) {T[x]=1; HT[x]=x;} //{T la tap cac dinh cua do thi G}
int dung=0;
while(dung==0)
{
//buoc 2
v=1; while(T[v]==0 && v<=n) v++; // tim v dau tien thuoc T
// Tim v thuoc T sao cho L[v] la nho nhat
for(j=v+1; j<=n; j++) if(T[j]==1 && L[j]<L[v]) v=j;
if(L[v]==MAXINT) {cout<<"\n DO THI KO LIEN THONG"; getch(); exit(1);}
T[v]=0; // loai v ra khoi tap T
//buoc 3
if (T[z]==0)
{
dung=1;
cout<<"\n duong di ngan nhat tu "<<a<<" den "<<z<<" la:"<<L[z];
// dua vao HT de in duong di
}
else
{
int r=L[x];
// xet cac dinh x thuoc T va ke v
for(x=1; x<=n; x++) if (T[x]==1 && w[x][v]!=MAXINT)
L[x]=min(L[x], L[v]+w[v][x]);
if (r!=L[x]) HT[x]=v; // cap nhat lai duong di den x

}
}
}
int main()
{
//clrscr();
docdlts();
for(int i=1; i<=n; i++)
{
cout<<"\n";

for(int j=1; j<=n; j++)
if(w[i][j]==MAXINT) {
//textcolor(2);
printf("%6c","c");
//textcolor(15);
}
else printf("%6d",w[i][j]);
}
dijkstra(1,9);
getch();
return 0;

}
file input:

Trích:

9 16
1 2 2
1 5 4
1 6 14
2 3 1
2 6 12
3 4 10
3 9 20
4 6 7
4 9 6
5 6 4
5 7 2
6 7 1
6 9 3
7 8 4
7 9 8
8 9 5


minhphuc 07-08-2010 12:52 AM

Ðề: C++: Thuật toán DIJKSTRA tìm đường đi ngắn nhất
 
Cái này là giải thuật tìm đường đi ngắn nhất!

Học môn này thiệt là lý thú, người giảng viên cũng thật là tuyệt vời!

Đề tài cuối khóa là tìm đường đi vận dụng cho xe cứu thương.

rcp 15-11-2011 01:04 AM

Ðề: C++: Thuật toán DIJKSTRA tìm đường đi ngắn nhất
 
Trích:

Nguyên văn bởi minhphuc (Gửi 39875)
Cái này là giải thuật tìm đường đi ngắn nhất!

Học môn này thiệt là lý thú, người giảng viên cũng thật là tuyệt vời!

Đề tài cuối khóa là tìm đường đi vận dụng cho xe cứu thương.


mình-rcp cũng đã "bị" phải học môn nì. Lúc đầu lớp học có khoảng ba mươi mấy sinh viên. Sau đợt thi cử giữa khóa còn hơn phân nửa số sv.

hihi.. đến kỳ thi cuối khóa chỉ còn mươi con nhạn là đà..

Chắc là tại.. do giáo sư giảng, gây mê làm sv ngủ gà ngủ gật..|-)

hihi.. họ đổ mừ[-(

--- rcp ---


Múi giờ GMT +8. Hiện tại là 06:38 AM.

Diễn đàn Đà Nẵng - DNG Forums
Member of DNG Group