#include <stdlib.h> #define MAXSIZE 100 #define MAXCOST 99 typedef struct { int vertex[MAXSIZE]; int edges[MAXSIZE][MAXSIZE]; } MyGraph; void GrarhPrint(MyGraph*g,int n); void CreateMGraph(MyGraph*g,int e,int n); void Djikstra(MyGraph *g,int v0,int n); void Ppath(int path[],int i,int v0); void Dispath(int dist[],int path[],int s[],int v0,int n); int main() { MyGraph *g=(MyGraph*)malloc(sizeof(MyGraph)); CreateMGraph(g,10,6); Djikstra(g,0,6); return 0; } void CreateMGraph(MyGraph*g, int e,//边数 int n //顶点数 ) { int i,j,k,m; printf("Input data of vertex(0~n-1):\n"); for(i=0; i<n; i++) { g->vertex[i]=i; //把顶点0~n-1保存的数组中 } //对顶点初始化，该开始都是没有通路 for(i=0; i<n; i++) { for(j=0; j<n; j++) { if(i==j) g->edges[i][j]=0; else g->edges[i][j]=MAXCOST;//99为不通 } } //输入通路，并确定边的权值 for(k=0; k<e; k++) { printf("Input edge of(i,j) and edge of size:"); scanf("%d%d%d",&i,&j,&m); g->edges[i][j]=m; } GrarhPrint(g,n); } //输出图 void GrarhPrint(MyGraph*g,int n) { int i=0; int j=0; for(i=0; i<n; i++) { for(j=0; j<n; j++) if(g->edges[i][j]==MAXCOST||i==j) printf("∞\t"); else printf("%d\t",g->edges[i][j]);//这里输入的是哪两个点之间有路径 printf("\n"); } } void Djikstra(MyGraph *g,int v0,int n) { int dist[MAXSIZE],path[MAXSIZE],s[MAXSIZE]; int i,j,k,mindis; for(i=0; i<n; i++) { dist[i]=g->edges[v0][i]; //V0到Vi的最短路径初值赋给dist[i] if(g->edges[v0][i]<MAXCOST)//路径初始化，MAXOST表示v0到vi没有边 path[i]=v0;//源点vo是vi当前最短路径中的前一个顶点 else path[i]=-1;//v0到vi没有边 s[i]=0;//s[i]=0表示顶点vi属于T集 } s[v0]=1;//v0并入集合S path[v0]=0;//v0的当前最短路径中无前一个顶点 for(i=0; i<n; i++) { mindis=MAXCOST; for(j=0; j<n; j++) //从当前集合T中选一个路径长度最短的顶点vk { if(s[j]==0&&dist[j]<mindis) { mindis=dist[j]; k=j; } } s[k]=1;//顶点vk加入集合S中 for(j=0; j<n; j++) //调整源点v0到集合T中任一顶点Vj的路径长度 { if(s[j]==0)//顶点Vj在集合T中 { if(g->edges[k][j]<MAXCOST && g->edges[k][j]+dist[k]<dist[j]) { //v0到Vj的长度大于V0到Vk和Vk到Vj的路径长度时 dist[j]=g->edges[k][j]+dist[k]; path[j]=k; } } } } Dispath(dist,path,s,v0,n); } void Ppath(int path[],int i,int v0) {//先序递归查找最短路径（源点为V0）上的顶点 int k; k=path[i]; if(k!=0)//顶点Vk不是源点V0时 { Ppath(path,k,v0);//递归查找顶点Vk的前一个顶点 printf("%d,",k);//输出顶点Vk } } void Dispath(int dist[],int path[],int s[],int v0,int n) { //输出最短路径 int i; for(i=0;i<n;i++) { if(s[i]==1)//顶点Vi在集合S中 { printf("从%d到%d的最短路径长度为:%d,路径为:",v0,i,dist[i]); printf("%d,",v0);//输出路径上的源点v0 Ppath(path,i,v0);//输出路径上的中间顶点Vi printf("%d\n",i);//输出路径上的终点 } else printf("从%d到%d不存在路径\n",v0,i); } }
Dijkstra算法：感觉就是从一个顶点i开始，把这个i顶点的到其他顶点的距离保存到一个数组中，数组下标为顶点号，先选择一个最小值，并把下标k记录下来，然后从选择的k顶点开始遍历k顶点距离其他顶点j的距离（不能再遍历i了）,把顶点i到顶点j的距离与顶点i到顶点k的距离+顶点k到j的距离的和比较，若大于则更新数组中顶点i到j的距离，否则不变；但要记得把路径记录下来，这个数组最终只是记录了从顶点i到其他顶点的最短距离，不能够记录经过哪些顶点，代码中数组dist记录的时最短路径，数组path记录的是经过的路径。