Xem bài viết đơn
  #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