迪杰斯特拉(Dijkstra)算法

              1 # include <stdio.h>
  2  3 # define MAX_VERTEXES 20//最大顶点数  4 # define INFINITY 65535;//代表∞  5  6 typedef struct  7 {/*    无向图结构体    */  8int vexs[MAX_VERTEXES];//顶点下标  9int arc[MAX_VERTEXES][MAX_VERTEXES];//矩阵 10int numVertexes, numEdges;//顶点数和边数 11 12}MGraph;
 13 14 typedef int PathArc[MAX_VERTEXES];//存储最短路径的下表数组 15 typedef int ShortPathTable[MAX_VERTEXES];//存储最短路径的权值数组 16 17void CreateMGraph (MGraph *G)
 18 {/*    创建 */ 19int i, j;
 20 21//printf ("请输入顶点数和边数"); 22     G->numVertexes = 9;//顶点 23     G->numEdges = 16;//边 24 25for (i=0; i<G->numVertexes; i++)
 26         G->vexs[i] = i;//初始化顶点下标 27 28for (i=0; i<G->numVertexes; i++)//初始化矩阵 29for (j=0; j<G->numVertexes; j++)
 30if (i == j)
 31                 G->arc[i][j] = 0;//本身则0 32else 33                 G->arc[i][j] = INFINITY;//否则为∞
 34 35//提前手动输入 36     G->arc[0][1]=1;
 37     G->arc[0][2]=5; 
 38     G->arc[1][2]=3; 
 39     G->arc[1][3]=7; 
 40     G->arc[1][4]=5; 
 41 42     G->arc[2][4]=1; 
 43     G->arc[2][5]=7; 
 44     G->arc[3][4]=2; 
 45     G->arc[3][6]=3; 
 46     G->arc[4][5]=3;
 47 48     G->arc[4][6]=6;
 49     G->arc[4][7]=9; 
 50     G->arc[5][7]=5; 
 51     G->arc[6][7]=2; 
 52     G->arc[6][8]=7;
 53 54     G->arc[7][8]=4;
 55 56for (i=0; i<G->numVertexes; i++)//无向图--矩阵上三角对称下三角 57for (j=i; j<G->numVertexes; j++)
 58if (i != j)
 59                 G->arc[j][i] = G->arc[i][j];
 60 61return ;
 62 63}
 64 65//P数组-存放最短路径顶点的下标，D数组-存放最短路径(权值) 66void Shorsequence_Path_Dijkstra (MGraph G, int v0, PathArc *P, ShortPathTable *D)
 67 {/*    迪杰斯特拉 算法 - 生成最短路径    */ 68int v, w, k, min;
 69int final[MAX_VERTEXES];    //final[w] = 1,表示求得顶点v0→vw的最短路径 70 71for (v=0; v<G.numVertexes; v++)
 72     {//初始化 73         final[v] = 0;            //全部顶点初始化为未知最短路径状态 74         (*D)[v] = G.arc[v0][v]; //和v0有连线的点加上权值 75         (*P)[v] = -1;            //初始化路径下标数组初始值为-1； 76    }
 77 78     (*D)[v0] = 0;                //v0→v0的路径-权值-为0 79     final[v0] = 1;                //v0→v0不需要求路径 80 81/*    开始主循环，每次循环求v0到某个v顶点的最短路径    */ 82for (v=1; v<G.numVertexes; v++)
 83    {
 84         min = INFINITY;            //初始化-目前所知离v0顶点的最近距离
 85 86//注意：这里不要想着w=v；因为程序执行的时候有的顶点不符合是直接跨过去了，然后置0是为了循环访问未访问的顶点 87for (w=0; w<G.numVertexes; w++)//查找和v0最近的顶点 88if (!final[w] && (*D)[w]<min)
 89             {//该顶点未被访问过，并且小于min 90                 k = w;            //k存入最近顶点的下标 91                 min = (*D)[w];    //min存入最短路径 92            }
 93 94         final[k] = 1;            //将目前找到最近的顶点-做标记 95 96for (w=0; w<G.numVertexes; w++)//目前找到与v0最近的顶点下标k，然后继续寻找与k顶点最近的下标 97if (!final[w] && (min+G.arc[k][w] < (*D)[w]))
 98             {//若顶点未被访问 并且    （目前最短路径(权值)v0→k + 目前最近的顶点(k)有关联的顶点路径(权值)）小于 v0有关联的权路径(权值) 99                 (*D)[w] = min + G.arc[k][w];//则与k顶点相关的权值+min--覆盖D数组100                 (*P)[w] = k;    //则与v0最近的顶点k顶点下标 给 P数组；101             }//(*D)[w] = min实际上就是上一个顶点和k顶点最短路径的 + arc[k][w]102    }
103104return ;
105}
106107int main (void)
108109{
110int i, j, v0;
111int number = 0;
112int sequence[MAX_VERTEXES][MAX_VERTEXES];
113    MGraph G;
114    PathArc P;
115     ShortPathTable D;                       //某点到各点的最短路径116     v0 = 0;
117118     CreateMGraph (&G);                       //创建119120     Shorsequence_Path_Dijkstra (G, v0, &P, &D);//迪杰斯特拉 算法 - 生成最短路径
121122//初始化正序输出的数组123for (i=0; i<G.numVertexes; i++)
124for (j=0; j<G.numVertexes; j++)
125             sequence[i][j] = 0;
126127/*    P数组-存放最短路径顶点的下标，D数组-存放最短路径(权值)    */128129     printf ("最短路径倒序如下：\n");
130for (i=1; i<G.numVertexes; i++)
131    {
132         printf ("v%d--v%d\t:  ", v0, i);
133         j = i;
134while (P[j] != -1)
135         {//若存在下一个顶点136             printf ("%d  ", P[j]);//则输出顶点137             j = P[j];//按顺序查找138             number ++;//记录(辅助正序输出)139        }
140141//离上一个顶点最近的顶点的下标-赋值给sequence数组142         j = i;
143while (0<number && P[j] != -1)
144        {
145             sequence[i][number--] = P[j];
146             j = P[j];
147        }
148         number = 0;
149         printf ("\n");
150    }
151152//自己修改的153     printf ("\n最短路径正序如下：\n");
154for (i=1; i<G.numVertexes; i++)
155    {
156         j = 1;
157         printf ("v%d--v%d\t:  ", v0, i);
158while (sequence[i][j] != 0)
159             printf ("%d   ", sequence[i][j++]);
160         printf ("\n");
161    }
162163     printf ("\n源点到各个点的最短路径为：\n");
164for (i=1; i<G.numVertexes; i++)
165         printf ("v%d--v%d  :  %d\n", G.vexs[0], G.vexs[i], D[i]);
166167return0;
168 }