• Hãy ủng hộ PhienBanMoi.Com bằng cách LIKE trang FANPAGE , GOOGLE+ dưới mỗi bài viết hoặc chia sẻ website nếu thấy hữu ích. Trân trọng cảm ơn!
  • [Thông Báo] Tuyển thành viên viết bài KIẾM TIỀN trên PhienBanMoi.Com


    Nhằm mục đích phát triển Phienbanmoi.com hơn nữa, có thêm các bài viết thông tin thực sự hữu ích từ những thành viên tích cực. BQT đã quyến định tạo ra cơ hội kiếm tiền từ các bài viết được đăng tải và chia sẻ trên diễn đàn

Nhờ Sửa hộ em cái code thuật toán dijkstra này với ạ :(((

killearrr

Member Chính Thức
Tham gia
13/5/14
Bài viết
25
Thích
3
#1
Nhờ anh chị nào giỏi xem và sửa hộ em cái này với ạ. Chạy mãi không được :((
[HASHTAG]#include[/HASHTAG]<conio.h>
[HASHTAG]#include[/HASHTAG]<stdio.h>
[HASHTAG]#define[/HASHTAG] vocuc 10000
int start,end,n,i,j;
int danhdau[100],trongso[100][100],chiphi[100];
int dinh[100]; //luu cac dinh da di qua
int duongdi[100];
void nhap_mang(int trongso[100][100], int n)
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("\tNhap phan tu dong %d cot %d: ",i,j);
scanf("%d",&trongso[j]);
}
}
}
void in_mang(int trongso[100][100], int n)
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d ",trongso[j]);
printf("\n");
}
}

void dijkstra()
{
int kt; //bien lap ,neu co chi phi nho nhat thi kt=0,neu tim dc chi phi nua thi kt=1 de tiep tuc buoc lap tim kiem
int k;//bien dung de lap
danhdau[end]=1;
chiphi[end]=0;
dinh[end]=0;
do
{
kt=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if((danhdau[j]==1)&&(trongso[j]!=vocuc)) //neu co duong di tu dinh nay den dinh kia
{
if(chiphi[j]+trongso[j]<chiphi)//so sanh chi phi dang xet tu dinh bd den dinh kt,
{
chiphi=chiphi[j]+trongso[j];//neu nho hon vo cuc ,thi cap nhat chi phi moi
dinh=j; //gan lai dinh dang xet
danhdau=1;
kt=1;
}
}
}while(kt==1);
if(chiphi[start]!=vocuc)
{
duongdi[1]=start;//duong di dau tien la dinh bat dau ,de sau nay in ra 1 -->2 hoac 2-->4
k=1;
while(dinh[duongdi[k]]!=0)
{
k++;
duongdi[k]=dinh[duongdi[k-1]];
}
printf("Duong di ngan nhat tu dinh %d --> %d la:\n\t\t",start,end);
for(i=1;i<k;i++)
printf("%d --> ",duongdi);
printf("%d\n",duongdi[k]);
printf("Do dai doan duong la: %d",chiphi[start]);
}
else
{
printf("Khong ton tai duong di tu dinh %d --> %d \n",start,end);
}
}
void khoitao()
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(trongso[j]==0)
trongso[j]=vocuc;
for(i=1;i<n;i++)
chiphi=vocuc;
}
int main ()
{
int n;
printf("NHAP n= ");
scanf("%d",&n);
printf("Nhap ma tran: \n");
nhap_mang(trongso,n);
printf("\nma tran da nhap: \n\n");
in_mang(trongso,n);
khoitao();
printf("\nNhap vao dinh xuat phat x=");scanf("%d",&start);
printf("Nhap vao dinh den y=");scanf("%d",&end);
dijkstra();

getch ();
}
 

Bài xem nhiều

Chia sẻ kiến thức - Download phần mềm