DỊCH VỤ THÀNH LẬP CÔNG TY TẠI ĐÀ NẴNG
DU LỊCH ĐÀ NẴNG THÀNH LẬP CÔNG TY SỞ HỮU TRÍ TUỆ TOUR
Trở lại   DIỄN ĐÀN ĐÀ NẴNG - DANANG FORUM > LIÊN MỤC: CÁC CÂU LẠC BỘ > CLB TIN HỌC > Góc lập trình > C/C++

Gởi Ðề Tài Mới  Trả lời
 
Ðiều Chỉnh Xếp Bài
  #1  
Cũ 25-06-2010, 10:14 PM
megaboy_dn's Avatar
megaboy_dn megaboy_dn vẫn chưa có mặt trong diễn đàn
Mộc Sơn
 
Tham gia ngày: Jan 2009
Đến từ: Đà Nẵng
Bài gởi: 129
Cảm ơn: 598
Được cảm ơn 528/104 bài viết
megaboy_dn is on a distinguished road
Gửi tin nhắn qua Yahoo chát tới megaboy_dn
Mặc định 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
Trả Lời Với Trích Dẫn
  #2  
Cũ 07-08-2010, 12:52 AM
minhphuc's Avatar
minhphuc minhphuc vẫn chưa có mặt trong diễn đàn
Thuỷ Sơn
 
Tham gia ngày: Oct 2008
Bài gởi: 599
Cảm ơn: 2,089
Được cảm ơn 1,169/412 bài viết
minhphuc is on a distinguished road
Mặc định Ðề: 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.

Trả Lời Với Trích Dẫn
  #3  
Cũ 15-11-2011, 01:04 AM
rcp's Avatar
rcp rcp vẫn chưa có mặt trong diễn đàn
Hỏa Sơn
 
Tham gia ngày: Oct 2008
Bài gởi: 1,440
Cảm ơn: 3,259
Được cảm ơn 2,482/927 bài viết
rcp is on a distinguished road
Mặc định Ðề: C++: Thuật toán DIJKSTRA tìm đường đi ngắn nhất

Trích:
Nguyên văn bởi minhphuc Xem Bài viế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.

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 ---
Trả Lời Với Trích Dẫn
Gởi Ðề Tài Mới  Trả lời


Ðang đọc: 1 (0 thành viên và 1 khách)
 
Ðiều Chỉnh
Xếp Bài

Chuyển đến

DNG Forum

Tel: 0236.3707404 - Hotline: 0915.888404
© Danang Travel - Managed by DNG Business

THÀNH LẬP CÔNG TY TẠI ĐÀ NẴNG | ĐĂNG KÝ NHÃN HIỆU TẠI ĐÀ NẴNG | ĐĂNG KÝ MÃ VẠCH TẠI ĐÀ NẴNG | BẢO HỘ NHÃN HIỆU TẠI ĐÀ NẴNG
Liên Lạc - DaNang Forum - Lưu Trữ - Lên Trên