文档介绍：合肥学院
计算机科学与技术系
课程设计报告
2009〜2010 学年第2学期
课
程
数据结构与算法
课程设计名称
Dijkstra算法的实现
学生
姓名
张睿辰
学
号
0804012044
专业
班级
图中实现求最短路径问题，第一步是要能成功的在内存中输入图的信息，图的信息有两个，一是顶点个数，二是每两点之间的权值信息。当建立图之后，对图进行遍历才能使用Dijkstra算法求出最短路径;在完成了图的建立之后，用Dijkstra 算法的思想，从单源点开始，求出到各个顶点的最短路径，并能够实现显示功能。程序流程图：
Dijkstra 算法流程图：
j为寻找下一个顶点的变量
三、详细设计和编码
邻接矩阵的定义：
我们定义全局变量cost[][],dist[]数组，方便在各子程序中的调用，加快了程序的运行速度。 int cost[MAX][MAX];
int dist[MAX];
int n;
cost二维数组用于存放邻接矩阵，每个位置代表的值为图中的权值，其余用无穷大999表示。 dist为辅助数组，图中每个顶点对应该数组中的一个元素，这个元素存放当前源点到该顶点的最短路径。此时的路径指示当前结果，并不一定是最终的最短路径。随着集合S的变化，其他顶点不断地加入到集合中，可能以这些新加入的顶点为“桥梁”产生比以前路径更短的路径，dist数组元素的值是动态变化的。
n 是指图中的顶点数目。
结点结构体的定义：
struct
{
int num;
int pnode[MAX];
}path[MAX];
整型变量num是用来记录求V0到每个顶点的最短路径时所经过的顶点的数目。数组 pnode 用来存放求 V0 到每个顶点的最短路径时所经过的顶点，初始为 V0。
结构体数组path为从V0到各顶点的最短路径。

初始化邻接矩阵 cost 中的值为无穷大，即任意两个顶点之间不存在路径。首先输入该有向图的顶点数n,然后依次输入各个顶点及边长（输入的顶点的序号应该小于顶点的数目）。输入0 0 0结束。定义变量contin，标志输入是否结束。若contin=1，输入继续，若contin=0，输入完成。
代码：
void creatgraph（） //创建带权有向图
{
int i,j,s,e,len,contin=1;
printf（"\n请输入顶点个数:”）；
scanf（"%d",&n）;
for（i=0；i<n；i++）
{
for（j=0；j<n；j++）{ cost[i][j]=up；
cost[j][i]=up； //初始化所有顶点间的边值均为无穷大 }
cost[i][i]=0； //每个顶点到自己的边值为 0
}
printf("输入各边，以0, 0, 0表示结束:\n");
i=1; //标志边的数目 while(contin==1)
{
printf("\t第％小条边->顶点，顶点，边长:",i); scanf("%d%d%d",&s,&e,&len);
if(s==0 && e==0 && len==0)
contin=0;
else if(s>=0 && s<n && e>=0 && e<n && len>0) //输入的顶点的序号应该小于顶点的数目 {
cost[s][e]=len;
i++;
}
else
printf("\t\t边值错误，重复输入!\n");
}
display(n);//输出所建数组 getchar();
}

在图的邻接矩阵显示中，分别利用for循环输出了矩阵的行列标，使矩阵很明了。
代码：
void display(int n1)
{
的邻接矩阵
int i,j;
printf("\n****************************** 所建图
\ f f \
**********************************\n");
for(i=0;i<n1;i++)
printf(" %d ",i); //利用for循环输出邻接矩阵的行标
printf("\n");
for(i=0;i<n1;i++)
{
printf("%d",i); 〃利用for循环输出邻接矩阵的列标
for(j=0;j<n1;j++)
printf("\t%3d<%d,%d>",cost[i][j],i,j);
printf("\n");
}
Dijkstra 求最短路径的实现
设图以邻接矩阵cost存储，矩阵中各元素的值为各边的权值。顶点间无边时其对应权值