文档介绍：编辑版word
页脚下载后可删除，如有侵权请告知删除！
编辑版word
云南财经大学信息学院学生综合性与设计性实验报告
（ 2013—2014 学年 第 2 学期 ）
周次：第7周 日期：2014年 4 月 17 日 地点：
班级
计专13-1
学生信息
学生1
成绩
学生2
实验名称
查看“”，选择熟悉的程序设计语言定义有向图，根据动画演示求取从有向图任一结点到其他结点的最短路径。
教师评语
该同学是否了解实验原理： □ □ □
该同学的实验能力： □ □ □
该同学的实验是否达到要求： □ □ □
实验报告是否规范： □ □ □
实验过程是否详细记录： □ □ □
教师签名：
年 月 日
一、实验内容与目的
查看“”，选择熟悉的程序设计语言定义有向图，根据动画演示求取从有向图任一结点 到其他结点的最短路径。
了解最短路径的概论，掌握求最短路径的方法。
二、实验原理或技术路线（可使用流程图描述）
实验原理：(李燕妮负责设计，周丽琼负责编程)
图是由结点的有穷集合V和边的集合E组成，求最短路径用迪杰斯特拉算法：
1)适用条件&范围：
编辑版word
页脚下载后可删除，如有侵权请告知删除！
编辑版word
a) 单源最短路径(从源点s到其它所有顶点v);
b) 有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图)
c) 所有边权非负(任取(i,j)∈E都有Wij≥0);
2)算法描述：
a)初始化：dis[v]=maxint(v∈V,v≠s); dis[s]=0; pre[s]=s; S={s};
b)For i:=1 to n
-S中的一顶点u使得dis[u]=min{dis[v]|v∈V-S}
=S+{u}
V-S中每个顶点v do Relax(u,v,Wu,v)
c)算法结束：dis[i]为s到i的最短距离；pre[i]为i的前驱节点
三、实验环境条件（使用的软件环境）
Microsoft Visual C++
实验方法、步骤（列出程序代码或操作过程）
/*本程序的功能是求图中任意两点间的最短路径*/
#include<>
#include<>
#include<>
#include<>
#define ING 9999
typedef struct ArcCell{
int adj;
/*顶点关系类型，用1表示相邻，0表示不相邻*/
}ArcCell,**AdjMatrix;