dijkstra-

Dijkstra算法

#include "stdio.h"  
main()  
{  
int N=3,INFINTY=1000;  
int i,j,k,u,v,w,min,zhongjian;  
int d[100],q[100]; 

int Garcs[100][100];  
 
int final[100],p[100][100];  

int vx=2,cout;  
 int baocun[100]; 

for (i=0;i<100;i++) 
{ 
baocun[i]=0; 
} 

for(i=0;i<N;i++)  
{  
for(j=0;j<N;j++)  
{  

printf("v%d -> ",i);  
printf("v%d ",j);  
scanf("%d",&Garcs[i][j]);  
if (Garcs[i][j] == -1) {Garcs[i][j]=INFINTY;} 
}  
}  


for(v=0;v<N;v++)  
{  
final[v]=0;  
d[v]=Garcs[0][v];  
 for(w=0;w<N;w++)  
p[v][w]=0;  

 if(d[v]<INFINTY)  
{  
 p[v][0]=1;p[v][v]=1;  
 }  
}  


 d[0]=0;final[0]=1;  


min=INFINTY; 
cout=0;  
int flag = 0; 
for(w=0;w<N;w++)  
{  

if(final[w]==0)  

{ 
if(Garcs[0][w]<min) 
{min = Garcs[0][w];u =w;}  

} 

} 
final[u] = 1; 
printf("%d",cout); 
for(j=0;j<cout;j++) 
{ 
for(k=0;k<cout-j;k++) 
{ 
if (baocun[k]<=baocun[k+1]) 
{ 
zhongjian=baocun[k]; 
baocun[k]=baocun[k+1]; 
baocun[k+1]=zhongjian; 
} 

} 

}
printf("%d",baocun[0]); 
for(v=0;v<N;v++)  
{  
if(final[v]==0&&(d[u]+Garcs[u][v]<d[v]))  
{  
d[w]=min+Garcs[w][v];  
q[w]=q[v];p[w][w]=1;  
}  

}  



return 0;
}