1.dijkstra算法实现
#include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> int edge[21][21]; int visit[21]; int dis[21]; #define INF 0x3f3f3f3f int dijkstra(int s,int e){ int i,j,k; memset(visit,0,sizeof(visit)); for(i=1;i<=20;i++){ //路径 dis[i]=INF; } dis[s]=0; int miniPos; for(j=1;j<=20;j++) { int min=INF; for(i=1;i<=20;i++){ if(!visit[i]&&dis[i]<min){ miniPos=i; min=dis[i]; } } visit[miniPos]=1; //从此处为起点 for(i=1;i<=20;i++){ if(!visit[i]&&dis[i]>dis[miniPos]+edge[miniPos][i]){ dis[i]=dis[miniPos]+edge[miniPos][i]; } } } return dis[e]; } int main(){ int n,m,x; int i,j; int T=1; while(scanf("%d",&n)!=EOF){ for(i=1;i<=20;i++){ for(j=1;j<=20;j++){ edge[i][j]=INF; } } for(j=1;j<=n;j++){ scanf("%d",&x); edge[1][x]=edge[x][1]=1; } for(i=2;i<=19;i++){ scanf("%d",&n); for(j=1;j<=n;j++){ scanf("%d",&x); edge[i][x]=edge[x][i]=1; } } if(scanf("%d",&m)){ int start,end; printf("Test Set #%d\n",T++); for(i=0;i<m;i++){ scanf("%d%d",&start,&end); int disss=dijkstra(start,end); printf("%d to %d: %d\n",start,end,disss); } printf("\n"); } } return 0; }
2、Floyd算法实现：
#include<stdio.h> #include<string.h> #define INF 0x3f3f3f3f #define LOCAL int edge[21][21]; int path[21][21]; void init(){ int i,j; for(i=1;i<=20;i++){ for(j=1;j<=20;j++){ edge[i][j]=INF; } } } int floyd(int s,int e){ int i,j,k; for(i=1;i<=20;i++){ for(j=1;j<=20;j++){ for(k=1;k<=20;k++){ if(edge[j][k]>edge[j][i]+edge[i][k]){ edge[j][k]=edge[j][i]+edge[i][k]; path[j][k]=i; } } } } return edge[s][e]; } void output(int i,int j){ if(path[i][j]==0){ printf("%d ",j); }else{ output(i,path[i][j]); output(path[i][j],j); } } int main(){ #ifdef LOCAL freopen("test.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif int i,j,n,x,m,t; int TT=1; while(scanf("%d",&n)!=EOF){ for(i=1;i<=20;i++){ for(j=1;j<=20;j++){ edge[i][j]=INF; } } for(i=1;i<=n;i++){ scanf("%d",&t); edge[1][t]=edge[t][1]=1; } for(i=2;i<=19;i++){ scanf("%d",&x); for(j=1;j<=x;j++){ scanf("%d",&t); edge[i][t]=edge[t][i]=1; } } if(scanf("%d",&m)){ int s,e; printf("Test Set #%d\n",TT++); for(i=0;i<m;i++){ scanf("%d%d",&s,&e); int ss=floyd(s,e); printf("\n%d to %d: %d\n",s,e,ss); //printf("%d ",s); //output(s,e); } printf("\n"); } } return 0; }