图结构
1 typedef struct arcell { //边的权值信息
2 int adj; //权值
3 } arcell,adjmatrix[MaxVertexNum][MaxVertexNum]; //图的邻接矩阵类型
4
5 typedef struct vexsinfo { //顶点信息
6 int position; //景点的编号
7 char name[32]; //景点的名称
8 char introduction[256]; //景点的介绍
9 } vexsinfo;
10
11 typedef struct mgraph { //图结构信息
12 vexsinfo vexs[MaxVertexNum]; //顶点向量(数组)
13 adjmatrix arcs; //邻接矩阵
14 int vexnum,arcnum; //分别指定顶点数和边数
15 } mgraph;
队列结构
1 #define TRUE 1
2 #define FALSE 0
3 #define OK 1
4 #define ERROR 0
5 #define INFEASIBLE -1
6 #define OVERFLOW -2
7 typedef int ElemType;
8 typedef int Status;
9 #define Queuesize 100
10 typedef struct{
11 ElemType *base;
12 int front,rear;
13 }SeQueue;//静态队列
14
15
16
17 Status InitQueue(SeQueue &Q){
18 Q.base=(ElemType *)malloc(Queuesize*sizeof(ElemType));
19 if(!Q.base) exit(OVERFLOW);
20 Q.front=Q.rear=0;
21 return OK;
22 }
23 Status QueueEmpty(SeQueue Q){
24 if(Q.front==Q.rear){
25 return OK;
26 }else{
27 return FALSE;
28 }
29 }
30 ElemType GetHead(SeQueue Q){
31 if(QueueEmpty(Q)) exit(ERROR);
32 return Q.base[Q.front];
33 }
34 Status EnQueue(SeQueue &Q,ElemType e){
35 if(Q.rear>=Queuesize) exit(OVERFLOW);
36 Q.base[Q.rear++]=e;
37 }
38 Status DeQueue(SeQueue &Q,ElemType e){
39 if(!QueueEmpty(Q)) exit(ERROR);
40 e=Q.base[Q.front++];
41 return OK;
42 }
43 Status QueueTraverse(SeQueue Q){
44 int i;
45 if(QueueEmpty(Q)) return ERROR;
46 for(i=Q.front;i<Q.rear;i++){
47 printf("%d",Q.base[i]);
48 }
49 return OK;
50 }
51 void copyQ(SeQueue &Q1,SeQueue Q2){
52 int i;
53 if(QueueEmpty(Q2)) return;
54 for(i=Q2.front;i<Q2.rear;i++){
55 EnQueue(Q1,Q2.base[i]);
56 }
57 }
严蔚敏版Dijkstra算法(稍有变动)
1 void shortestpath_dij(mgraph c)
2 {
3 //迪杰斯特拉算法，求从顶点v0到其余顶点的最短路经及其带权长度d[v]
4 //若p[v][w]为1，则w是从v0到v的最短路经上的顶点
5 //final[v]类型用于设置访问标志
6
7 int v,w,i,min,t=0,x,flag=1,v0; //vo为起始景点的编号
8 int final[50],d[50],p[50][50];
9 printf("\n请输入一个起始景点的编号：");
10 scanf("%d",&v0);
11 printf("\n\n");
12 while(v0<0||v0>c.vexnum)
13 {
14 printf("\n你所输入的景点编号不存在\n");
15 printf("请重新输入：");
16 scanf("%d",&v0);
17 }//while
18 for(v=0;v<c.vexnum ;v++)
19 {
20 final[v]=0; //初始化各顶点访问标志
21 d[v]=c.arcs[v0][v].adj; //v0 到各顶点 v 的权值赋值给d[v]
22 for(w=0;w<c.vexnum ;w++) //初始化p[][]数组，各顶点间的路径全部设置为空路径0
23 p[v][w]=0;
24 if(d[v]<Infinity) //v0 到v 有边相连，修改p[v][v0]的值为1
25 {
26 p[v][v0]=1;
27 p[v][v]=1; //各顶点自己到自己要连通
28 }
29 }//for
30 d[v0]=0; //自己到自己的权值设为0
31 final[v0]=1; //v0的访问标志设为1，v 属于 s 集
32 for(i=1;i<c.vexnum ;i++) //对其余c.vexnum-1个顶点w，依次求 v 到 w 的最短路径
33 {
34 min=Infinity;
35 for(w=0;w<c.vexnum ;w++) //在未被访问的顶点中，查找与 v0 最近的顶点v
36 if(!final[w])
37 if(d[w]<min) //v0 到 w (有边)的权值<min
38 {
39 v=w;
40 min=d[w];
41 }//if
42 final[v]=1; //v 的访问标志设置为1，v 属于s集
43 for(w=0;w<c.vexnum ;w++) //修改v0 到其余各顶点w 的最短路径权值d[w]
44 if(!final[w]&&(min+c.arcs[v][w].adj <d[w])) //若w 不属于s，且v 到w 有边相连
45 {
46 d[w]=min+c.arcs[v][w].adj; //修改v0 到w 的权值d[w]
47 for(x=0;x<c.vexnum ;x++) //所有v0 到v 的最短路径上的顶点x，都是v0 到w 的最短路径上的顶点
48 p[w][x]=p[v][x];
49 p[w][w]=1;
50 }//if
51 }//for
52 for(v=0;v<c.vexnum ;v++) //输出v0 到其它顶点v 的最短路径
53 {
54 if(v!=v0)
55 printf("%s",c.vexs[v0].name); //输出景点v0 的景点名
56 for(w=0;w<c.vexnum ;w++) //对图中每个顶点w，试探w 是否是v0 到v 的最短路径上的顶点
57 {
58 if(p[v][w] && w!=v0 && w!=v) //若w 是且w 不等于v0，则输出该景点
59 printf("--->%s",c.vexs[w].name);
60
61 }
62 printf("---->%s",c.vexs[v].name);
63 printf("\n总路线长为%d米\n\n",d[v]);
64
65
66
67 }//for
68 }//shortestpath
在p[][]数组中确实存储了对于每一个点的最短路径，但在输出的时候出现了路径错误的问题（上图的53-67行）。通过对顶点较少的图的分析，发现了路径的顺序取决于顶点的标号，因此出现了路径不知道谁先谁后的问题。特此采用队列结构来解决此问题。
对以上标红的代码进行替换
1 void shortestpath_dij(mgraph c)
2 {
3 //迪杰斯特拉算法，求从顶点v0到其余顶点的最短路经及其带权长度d[v]
4 //若p[v][w]为1，则w是从v0到v的最短路经上的顶点
5 //final[v]类型用于设置访问标志
6
7 int v,w,i,min,t=0,x,flag=1,v0; //vo为起始景点的编号
8 int final[50],d[50];
9 SeQueue p[50];
10 printf("\n请输入一个起始景点的编号：");
11 scanf("%d",&v0);
12 printf("\n\n");
13 while(v0<0||v0>c.vexnum)
14 {
15 printf("\n你所输入的景点编号不存在\n");
16 printf("请重新输入：");
17 scanf("%d",&v0);
18 }//while
19 for(v=0;v<c.vexnum ;v++)
20 {
21 final[v]=0; //初始化各顶点访问标志
22 d[v]=c.arcs[v0][v].adj; //v0 到各顶点 v 的权值赋值给d[v]
23 InitQueue(p[v]);
24 }//for
25 d[v0]=0; //自己到自己的权值设为0
26 final[v0]=1; //v0的访问标志设为1，v 属于 s 集
27 for(i=1;i<c.vexnum ;i++) //对其余c.vexnum-1个顶点w，依次求 v 到 w 的最短路径
28 {
29 min=Infinity;
30 for(w=0;w<c.vexnum ;w++) //在未被访问的顶点中，查找与 v0 最近的顶点v
31 if(!final[w])
32 if(d[w]<min) //v0 到 w (有边)的权值<min
33 {
34 v=w;
35 min=d[w];
36 }//if
37 final[v]=1; //v 的访问标志设置为1，v 属于s集
38 for(w=0;w<c.vexnum ;w++) //修改v0 到其余各顶点w 的最短路径权值d[w]
39 if(!final[w]&&(min+c.arcs[v][w].adj <d[w])) //若w 不属于s，且v 到w 有边相连
40 {
41 d[w]=min+c.arcs[v][w].adj; //修改v0 到w 的权值d[w]
42 copyQ(p[w],p[]);
43 EnQueue(p[w],v);
44 }//if
45 }//for
46 for(v=0;v<c.vexnum ;v++) //输出v0 到其它顶点v 的最短路径
47 {
48 if(v!=v0)
49 printf("%s",c.vexs[v0].name); //输出景点v0 的景点名
50 for(i=p[v].front;i<p[v].rear;i++){
51 printf("--->%d,%s",c.vexs[p[v].base[i]].position,c.vexs[p[v].base[i]].name);
52 }
53 printf("--->%d,%s",c.vexs[v].position,c.vexs[v].name);
54 printf("\n总路线长为%d米\n\n",d[v]);
55 }//for
56 }//shortestpath