#include<stdio.h> #define M 20//边数 #define N 10//顶点数 #define MAX 10000 void Dijkstra(int v, int dist[][N],int D[N],int p[N],int s[N]) ; int flag[N]={0}; int flag1=0; int flag2=0; typedef struct { int startvex; int endvex; int length; }edge;//边的结构体 edge T[M]; void main() { int dist[N][N]={{0,MAX,MAX,MAX,MAX,1,MAX,MAX,MAX,MAX},//图的邻接矩阵 {MAX,0,MAX,MAX,MAX,MAX,1,1,MAX,MAX}, {MAX,MAX,0,MAX,MAX,1,1,MAX,1,MAX}, {MAX,MAX,MAX,0,MAX,MAX,MAX,1,1,MAX}, {MAX,MAX,MAX,MAX,0,MAX,MAX,1,MAX,1}, {1,MAX,1,MAX,MAX,0,MAX,MAX,MAX,MAX}, {MAX,1,1,MAX,MAX,MAX,0,MAX,MAX,MAX}, {MAX,1,MAX,1,1,MAX,MAX,0,MAX,MAX}, {MAX,MAX,1,1,MAX,MAX,MAX,MAX,0,MAX}, {MAX,MAX,MAX,MAX,1,MAX,MAX,MAX,MAX,0} }; int D[N]={0}; int p[N]={0}; int s[N]={0}; int num=0; Dijkstra(0,dist,D, p,s) ;//0表示从状态(1111)开始 } void Dijkstra(int v, int dist[][N],int D[N],int p[N],int s[N]) { int i, j, k, v1, min, max=10000, pre; /* Max中的值用以表示dist矩阵中的值?*/ v1=v; for( i=0; i<N; i++) /* 各数组进行初始化*/ { D[i]=dist[v1][i]; if( D[i] != MAX ) p[i]= v1+1; else p[i]=0; s[i]=0; } s[v1]=1; /* 将源点送U */ for( i=0; i<N-1; i++) /* 求源点到其余顶点的最短距离*/ { min=10001; /* min>max, 以保证值为?的的的的顶顶顶顶点点点点也也也也能能能能加加加加入入入入U */ for( j=0; j<N-1; j++) if ( ( !s[j] )&&(D[j]<min) ) /* 找出到源点具有最短距离的边*/ {min=D[j]; k=j; } s[k]=1; /* 将找到的顶点k送入U */ for(j=0; j<N; j++) if ( (!s[j])&&(D[j]>D[k]+dist[k][j]) ) /* 调整V-U中各顶点的距离值*/ {D[j]=D[k]+dist[k][j]; p[j]=k+1; /* k是j的前趋*/ } } /* 所有顶点已扩充到U中*/ for( i=0; i<N; i++) { printf(" %d : %d ", D[i], i); pre=p[i]; while ((pre!=0)&&(pre!=v+1)) { printf ("<- %d ", pre-1); pre=p[pre-1]; } printf("<-%d \n", v); } }
#include<stdio.h> #define N 10 //顶点个数 #define MAX 10000 void Floyd(int dist[N][N],int A[N][N],int path[N][N]) { for(int i=0;i<N;i++) for(int j=0;j<N;j++) for(int k=0;k<N;k++) { /*if(A[i][j]>(A[i][k]+dist[k][j]))//方法一:计算每一次矩阵 { A[i][j]=(A[i][k]+dist[k][j]); path[i][j]=path[k][j]; }*/ if(A[i][j]>(A[i][k]+A[k][j]))//方法二:计算的幂次矩阵 { A[i][j]=(A[i][k]+A[k][j]); path[i][j]=path[k][j]; } } } void main() { int dist[N][N]={{0,MAX,MAX,MAX,MAX,1,MAX,MAX,MAX,MAX},//图的邻接矩阵 {MAX,0,MAX,MAX,MAX,MAX,1,1,MAX,MAX}, {MAX,MAX,0,MAX,MAX,1,1,MAX,1,MAX}, {MAX,MAX,MAX,0,MAX,MAX,MAX,1,1,MAX}, {MAX,MAX,MAX,MAX,0,MAX,MAX,1,MAX,1}, {1,MAX,1,MAX,MAX,0,MAX,MAX,MAX,MAX}, {MAX,1,1,MAX,MAX,MAX,0,MAX,MAX,MAX}, {MAX,1,MAX,1,1,MAX,MAX,0,MAX,MAX}, {MAX,MAX,1,1,MAX,MAX,MAX,MAX,0,MAX}, {MAX,MAX,MAX,MAX,1,MAX,MAX,MAX,MAX,0} }; int A[N][N]; int path[N][N]={0};//给出两顶点间的路径 int pre=0; for(int i=0;i<N;i++) for(int j=0;j<N;j++) { A[i][j]=dist[i][j]; if(dist[i][j]!=MAX) path[i][j]=i+1; else path[i][j]=0; } for(int k=0;k<7;k++)//若用方法一,需循环N-3次,若用方法二,需要循环lg(N-1)次 Floyd(dist,A,path); printf("每对顶点间的最短路径矩阵为:\n"); for(int i=0;i<N;i++) { for(int j=0;j<N;j++) printf("%d ",A[i][j]); printf("\n"); } printf("\n每对顶点的具体最短路径为:\n"); for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { printf("%d: %d ",A[i][j],j+1); pre=path[i][j]; while((pre!=0)&&(pre!=i+1)) { printf("<- %d ",pre); pre=path[i][pre-1]; } printf(" <- %d\n",i+1); } } }
原文:http://blog.csdn.net/tengweitw/article/details/25296257