-
25-02-2011, 07:26 PM #1Junior Member
- Ngày tham gia
- Sep 2015
- Bài viết
- 0
Tìm đường đi ngắn nhất bằng giải thuật dijkstra trong lập trình C
Em mới học dev C,mấy anh giúp em bài tập này với .||Tìm đường đi ngắn nhất bằng giải thuật dijkstra...?||Em có đoạn code này mấy anh coi dùm em có đúng không,chỉnh sửa lại giúp em với....||#include<conio.h>
#include<stdio.h>
#define vc 32767
int x,y,n,chuaxet[50],c[30][30],T[20],s[30];
void nhapmt ();
void khoitao ();
void xuatmt ();
void timduong ();
main(){
do{ printf("
nhap n=");
scanf("%d",&n);
}
while(n<0||n>30);
nhapmt();
xuatmt();
khoitao();
printf("
nhap vao dinh xuat phat x=");
scanf("%d",&x);
printf("
nhap vao dinh den y=");
scanf("%d",&y);
timduong();
getch();
}
void nhapmt(){
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{printf("c[%d][%d]=",i,j);
scanf("%d",&c[i][j]);
}
}
void xuatmt(){
for(int i=1;i<=n;i++)
{ for(int j=1;j<=n;j++) printf("%2d",c[i][j]);
printf("
");
}
}
void khoitao(){
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) if(c[i][j]==0) c[i][j]=vc;
for(i=1;i<=n;i++) s[i]=vc;
}
void timduong(){
int kt,k,b[20];
int i,j;
chuaxet[y]=1;s[y]=0;T[y]=0;
do { kt=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) if((chuaxet[j]==1)&&(c[i][j]!=vc))
{ if(s[j]+c[i][j]<s[i])
{ s[i]=s[j]+c[i][j];
T[i]=j;
chuaxet[i]=1;
kt=1;
}
}
}while(kt==1);
if(s[x]!=vc)
{
b[1]=x;k=1;
while(T[b[k]]!=0)
{
k++;
b[k]=T[b[k-1]];
}
printf("\tDuong di ngan nhat tu dinh %d --> %d la:
\t\t",x,y);
for(i=1;i<k;i++)
printf("%d -->",b[i]);
printf("%d
",b[k]);
printf("\t\tDo dai doan duong la:%d",s[x]);
}
else
{
printf("\tKhong ton tai duong di tu dinh %d --> %d
",x,y);
}
getch();
}View more random threads:
Thông qua phân tích dữ liệu Google từ 86 quốc gia, mới đây, một công ty tại Anh đã công bố bảng xếp hạng kích tấc "cậu nhỏ" của các nước trên thế giới. Kết quả, hầu hết các nước xếp ở nhóm đầu của...
"Chim" của chàng trai Việt thuộc...