求单源最短路径—Dijkstra算法实验报告.docx

本科学生综合性实验报告
项目组长 杨滨 学号 0123707
成 员 杨滨
专 业 软件工程 班级12软件2班
实验项目名称 求单源最短路径一Dijkstra算法
指导教师及职称—赵晓平讲师_____
开课学期 13至14学年一学期
上课时间 2013 年 9 月 1 日
学生实验报告三（综合性实验）
学生姓名
杨滨 学号 0123707
同组人
实验项目
求单源取短路栓 Dijkstra算法
3必修 □选修 □演示性实验□验证性实验 □操作性实验 □综合性实验
实验地点
W101
实验仪器台号
指导教师
赵晓平
实验日期及节次
2013. 12. 17(二)12 节
2013. 12. 19(—) 89A 节
实验综述
1、实验訂的及要求
（1） 了解求最优化问题的贪心算法，了解贪心法的基本要素，学会如何使用贪 心策略设计算法；
（2） 了解单源最短路径问题，掌握Dijkstra算法的思想:
（3）编写程序,利JU Dijkstra算法实现,求任 意两点间的单源最短路径。
实验题：
给出如右有向图的边权图,求任意两点间的单源 最短路径。
实验要求：
认真完成实验题，能正确运行，提交实验报告并 上传程序，实验报告要求写出操作步骤、结果、问题、 解决方法、体会等。
2、实验仪器、设备或软件
计算机、VC++、。
二、实验过程(实验步骤、记录、数据、分析)
#include<iostream>
using namespace std;
Avoid Graph(int n, bool *inS, int a[6. 16], int *d)
{
inS=new bool In]:
inS[0]=0;
for(int i=l;i<n;i++)
inS[i]=l;
a=new int*[n];
for(i=0;i<n;i++)
a[i]=new int[n];
cout<<，zinput //<<endl;
for(i=0;i<n;i++)
for (int j二0;j〈n;j++)
cin»a[i] [j];
d=new int .n];
for(i=0;i<n;i++)
d[i]二 a[0][i];
}*/
int Choose(int n,int *d, bool *s)
int i, minpos=-l, min=500;
for(i=l;i<n;i++)
if(d[i]<min && ! s [i ])
{ min=d[i];minpos=i; }
return minpos;
}
void Di jkstra(int s, int n, bool *i nS, int *d, int * path, int a_6_ [6])
{
int k, i, j ;
for(i=0;i<n;i++)
{
inS[i]二false;d[i]二a[s][i];
if(i!=s && d[i]<500) path[i]=s;
else path[i]=-l:
}
inS[s]=true;d[s]=0;
for(i=0;i<n-l;i++)
{
k=Choose (