数据结构（最短路径）

 1 #define MAXVEX 9//宏定义图的最大定点数
 2 #define INFINITY 65535//路不通时的默认值
 3 
 4 typedef int Patharc[MAXVEX]//用于存储最段路经下标的数据
 5 typedef int ShortPathTable[MaxVEX]//用于存储到各点的最短路径的权值和
 6 
 7 //G:图结构：are，矩阵二维数组；numVertexes，图中顶点数
 8 //A:用于传入源点
 9 //P就是Patharc数组，用于存储源点到下标位置对应顶点为终点的最短路径的倒数第二个顶点的下标（最段路经终点的前驱）
10 //D就是ShortPathTable数组，用于存储各源点A到其他各点的最短路径权之和
11 void ShortestPath_Dijkstar(MGraph G,int A,patharc *P,ShortPathTable *D){
12     int v,w,k,min;
13     int final[MAXVEX];//标记数组：用于标志是否已经找到源点到对定位置的最段路经【0表示未找到，1表示已经找到】
14     
15     //初始化数据
16     for(v=0;v<G.numVertexes;v++){
17         final[v]=0;//全部顶点初始化为未找到最段路泾
18         (*D)[v]=G.are[A][v];//因为寻找A下标顶点到各顶点的最短路径，所以初始化时就是为矩阵中第v行的数据（这行数据就是这个顶点到各顶点的权）
19         (*P)[v]=0;//初始化路径数组为0
20     }
21     (*D)[A]=0;//源点到源点的路径权为0
22     final[A]=1;//源点到源点的路径已经找到
23 
24     //开始循环，找源点到其他[G.numVertexes-1]个顶点的最短路径
25     for(v=1;v<G.numVertexes;v++){//【循环1】：循环一次找到一个源点到其他点【X】的最短路径
26         min=INFINITY;
27         for(w=0;w<G.numVertexes;w++){
28             if(!final[w] && (*D)[w]<min){//在未找到最短路径的顶点中找当前距离源点权最近的那个顶点，这个顶点就是【循环1】本次循环所找到的【X】
29                 k=w;//记录这次找到最短路径的终点下标
30                 min=(*D)[w];//记录这次找到点的最短路径的权（这里的权就是这条路径的权之和）
31             }
32         }
33         final[k]=1;//标记源点到该顶点为终点的最短路径已经找
34 
35         //修正当点进度源点到各点的最短距离；因为为源点多加了一条边，就为源点到各点添加了若干条路，这些路会有刷新源点到其他点的最短距离
36         for(w=0;w<G.numVertexes;w++){
37             //未找最短路径到的顶点【Y】中；从源点到【X】再到【Y】的距离小于原先距离，就刷新了原先到【Y】的距离
38             if(!final[w] && (min+G.arc[k][w] < (*D)[w])){
39                 (*D)[w]=min+G.arc[k][w];//刷新该距离
40                 (*P)[w]=k;//记录刷新到w顶点的最短距离的顶点，也是这条当前最短距离路径的前驱
41             }
42         }
43     }
44 }

 1 #define MAXVEX 9//宏定义图的最大定点数
 2 #define INFINITY 65535//路不通时的默认值
 3 
 4 typedef int Pathmatirx[MAXVEX][MAXVEX]//用于存储最段路经下标的数据
 5 typedef int ShortPathTable[MaxVEX][MaxVEX]//用于存储到各点的最短路径的权值和
 6 
 7 void ShortesPath_Floyd(MGraph G,Pathmatirx *D,ShortPathTable *D){
 8     int v,w,k;
 9     //初始化D和P
10     for(v=0;V<G.numVertexes;v++){
11         for(w=0;w<G.numVertexes;w++){
12             (*D)[v][w]=G.matirx[v][w];
13             (*P)[v][w]=w;
14         }
15     }
16 
17     //弗洛伊德算法
18     for(k=0;k<G.numVertexes;k++){
19         for(v=0;v<G.numVertexes;v++){
20             for(w=0;w<G.numVertexes;w++){
21                 if( (*D)[v][w] > (*D)[v][w] + (*D)[k][w] ){
22                     (*D)[v][w]=(*D)[v][w]+(*D)[k][w];
23                     (*P)[v][w]=(*P)[v][k];
24                 }
25             }
26         }
27     }
28 }
29 
30 void printPath(MGraph G,int u,int v,int Pathmatirx[][MAXVEX]){
31     int mid;
32     if(Pathmatirx[u][v]==-1)
33         printf("<%c,%c>  ",G.lin[u],G.lin[v]);
34     else{
35         mid= Pathmatirx[u][v];
36         printPath(G,u,mid,Pathmatirx);
37         printPath(G,mid,v,Pathmatirx);
38     }
39 }