单源最短路径问题实验参考报告

实验题目：单源最短路径问题2010年11月18日告诉您寝的人下周二（13周）做实验记得写~~~~

实验目的：

1．明确单源最短路径问题的概念；

2．利用贪心算法解决单源最短路径问题；

3．通过本例熟悉贪心算法在程序设计中的应用方法。

实验内容

给定一个带权有向图G=(V,E),其中每条边的权是非负实数。另外，还给定V 中的一个顶点，称为源。现在要计算从源到所有其他各点的最短路长度。

实验原理

在贪心算法中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策。

Dijkstra算法是解决单源最短路径问题的贪心算法。设置顶点集合S并不断作

贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径已知。初始时S中只含源。设u为G中一顶点，从源点到u且中间只经过S中的顶点的路称为从源到u特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。每次从V-S选出具有最短特殊路径长度的顶点u，将u添加到S中，同时对特殊路径长度进行必要的修改。一旦V=S，就得到从源到其他所有顶点的最短路径，也就得到问题的解。

算法实现

#include

using namespace std;

#define MAX 999

void getdata(int **c,int n)

{

int i,j;

int begin,end,weight;

for (i=1;i<=n;i++)

{

for (j=1;j<=n;j++)

{

if(i==j)

c[i][j]=0;

else

c[i][j]=MAX;

}

}

do {

cout<<"请输入起点终点权值(-1退出)：";

cin>>begin;

if(begin==-1) break;

cin>>end>>weight;

c[begin][end]=weight;

} while(begin!=-1);

}

void Dijkstra(int n,int v ,int *dist,int *prev,int **c)

{

bool s[MAX];

int i,j;

for (i=1;i<=n;i++)

{

dist[i]=c[v][i]; //从源点到各点的值

s[i]=false;

if(dist[i]==MAX) prev[i]=0; //最大值没有路径

else prev[i]=v; //前驱为源点

}

dist[v]=0;s[v]=true;

for (i=1;i<=n;i++)

{

int temp=MAX;

int u=v;

for(j=1;j<=n;j++)

if((!s[j])&&(dist[j]

s[u]=true;

for (j=1;j<=n;j++)

{

if((!s[j])&&(c[u][j]

{

int newdist=dist[u]+c[u][j];

if(newdist

}

}

}

}

void PrintPath(int *prev,int n,int begin,int end)

{

int *path=new int [n+1];

int i,m=n;

bool k=true;

path[end]=end;

for(i=end-1;i>1;i--)

{

path[i]=prev[path[i+1]]; //构造路径

m--;

}

for (i=m;i<=end;i++) {

cout<"; //输出路径}

cout<<"\b\b"<<" "<

}

void main()

{

int n,i;

int v=1;

cout<<"请输入顶点个数：";

cin>>n;

int *dist=new int [n+1];

int *prev=new int [n+1];

int **c;

c=new int *[n+1];

for (i=0;i<=n;i++)

{

c[i]=new int [n+1];

}

getdata(c,n); //获取数据

int begin=1,end;

cout<<"请输入所求单源路径的起点终点：";

cin>>begin>>end;

v=begin;

Dijkstra(n,v,dist,prev,c); //计算路径

PrintPath(prev,n,begin,end); //输出路径

}

实验思考题：

1.简述贪心算法的基本思想及算法实现过程？

基本思路:

1.建立数学模型来描述问题。

2.把求解的问题分成若干个子问题。

3.对每一子问题求解，得到子问题的局部最优解。

4.把子问题的解局部最优解合成原来解问题的一个解。

算法实现过程：

1.从问题的某一初始解出发；

2.当能朝给定总目标前进一步，求出可行解的一个解元素；

3.由所有解元素组合成问题的一个可行解。

实验三 最短路径的算法(离散数学实验报告)

实验3：最短路径算法 一、实验目的 通过本实验的学习，理解Floyd（弗洛伊得）最短路径算法的思想 二、实验内容 用C语言编程实现求赋权图中任意两点间最短路径的Floyd算法，并能对给定的两结点自动求出最短路径 三、实验原理、方法和手段 1、Floyd算法的原理 定义：Dk[i,j] 表示赋权图中从结点vi出发仅通过v0，v1，┉，vk-1中的某些结点到达vj的最短路径的长度， 若从vi到vj没有仅通过v0，v1，┉，vk-1 的路径，则D[i,j]=∝即 D-1[i,j] 表示赋权图中从结点vi到vj的边的长度，若没有从结点vi到vj的边，则D[i,j]=∝ D0[i,j] 表示赋权图中从结点vi到vj的”最短”路径的长度, 这条路上除了可能有v0外没有其它结点 D1[i,j] 表示赋权图中从结点vi到vj的”最短”路径的长度, 这条路上除了可能有v0，v1外没有其它结点 ┉┉┉ 根据此定义，D k[i,j]=min{ D k-1[i,j] , D k-1[i,k-1]+D k-1[k-1,j] } 定义：path[i,j]表示从结点vi到vj的“最短”路径上vi的后继结点 四、实验要求 要求输出每对结点之间的最短路径长度以及其最短路径 五、实验步骤 （一）算法描述 Step 1 初始化有向图的成本邻矩阵D、路径矩阵path 若从结点vi到vj有边，则D[i,j]= vi到vj的边的长度，path[i,j]= i； 否则D[i,j]=∝，path[i,j]=-1 Step 2 刷新D、path 对k=1,2,┉n 重复Step 3和Step 4 Step 3 刷新行对i=1,2,┉n 重复Step 4 Step 4 刷新Mij 对j=1,2,┉n 若D k-1[i,k]+D k-1[k,j]

实验报告

算法与数据结构 实验报告 系（院）：计算机科学学院 专业班级：软工11102 姓名：潘香杰 学号： 201104449 班级序号： 18 指导教师：詹泽梅老师 实验时间：2013.6.17 - 2013.6.29 实验地点：4号楼5楼机房

目录 1、课程设计目的．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 2、设计任务．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 3、设计方案．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 4、实现过程．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 5、测试．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 6、使用说明．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 7、难点与收获．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 8、实现代码．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 9、可改进的地方．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．

算法与数据结构课程设计是在学完数据结构课程之后的实践教学环节。本实践教学是培养学生数据抽象能力，进行复杂程序设计的训练过程。要求学生能对所涉及问题选择合适的数据结构、存储结构及算法，并编写出结构清楚且正确易读的程序，提高程序设计基本技能和技巧。 一．设计目的 1．提高数据抽象能力。根据实际问题，能利用数据结构理论课中所学到的知识选择合适的逻辑结构以及存储结构，并设计出有效解决问题的算法。 2．提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 3．初步了解开发过程中问题分析、整体设计、程序编码、测试等基本方法和技能。二．设计任务 设计一个基于DOS菜单的应用程序。要利用多级菜单实现各种功能。内容如下： ①创建无向图的邻接表 ②无向图的深度优先遍历 ③无向创建无向图的邻接矩阵 ④无向图的基本操作及应用 ⑤图的广度优先遍历 1．有向图的基本操作及应用 ①创建有向图的邻接矩阵 ②创建有向图的邻接表 ③拓扑排序 2．无向网的基本操作及应用 ①创建无向网的邻接矩阵 ②创建无向网的邻接表 ③求最小生成树 3．有向网的基本操作及应用 ①创建有向网的邻接矩阵 ②创建有向网的邻接表 ③关键路径 ④单源最短路径 三．设计方案 第一步：根据设计任务，设计DOS菜单，菜单运行成果如图所示：

MATLAB实验报告,遗传算法解最短路径以及函数最小值问题讲解

硕士生考查课程考试试卷 考试科目：MATLAB教程 考生姓名：考生学号： 学院：专业： 考生成绩： 任课老师(签名) 考试日期：20 年月日午时至时

《MATLAB 教程》试题： A 、利用MATLA B 设计遗传算法程序，寻找下图11个端点的最短路径，其中没有连接的端点表示没有路径。要求设计遗传算法对该问题求解。 a d e h k B 、设计遗传算法求解f (x)极小值，具体表达式如下： 3 21231(,,)5.12 5.12,1,2,3 i i i f x x x x x i =?=???-≤≤=? ∑ 要求必须使用m 函数方式设计程序。 C 、利用MATLAB 编程实现：三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行，随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货，但是如何乘船渡河的大权掌握在商人手中，商人们怎样才能安全渡河？ D 、结合自己的研究方向选择合适的问题，利用MATLAB 进行实验。 以上四题任选一题进行实验，并写出实验报告。

选择题目： A 一、问题分析（10分） 1 4 10 11 如图如示，将节点编号，依次为 1.2.3.4.5.6.7.8.9.10.11，由图论知识，则可写出其带权邻接矩阵为： 0 2 8 1 500 500 500 500 500 500 500 2 0 6 500 1 500 500 500 500 500 500 8 6 0 7 500 1 500 500 500 500 500 1 500 7 0 500 500 9 500 500 500 500 500 1 500 500 0 3 500 2 500 500 500 500 500 1 500 3 0 4 500 6 500 500 500 500 500 9 500 4 0 500 500 1 500 500 500 500 500 2 500 500 0 7 500 9 500 500 500 500 500 6 500 7 0 1 2 500 500 500 500 500 500 1 500 1 0 4 500 500 500 500 500 500 500 9 2 4 0 注：为避免计算时无穷大数吃掉小数，此处为令inf=500。 问题要求求出任意两点间的最短路径，Floyd 算法采用的是在两点间尝试插入顶点，比较距离长短的方法。我思考后认为，用遗传算法很难找到一个可以统一表示最短路径的函数，但是可以对每一对点分别计算，然后加入for 循环，可将相互之间的所有情况解出。观察本题可发现，所有节点都是可双向行走，则可只计算i 到j 的路径与距离，然后将矩阵按主对角线翻折即可得到全部数据。 二、实验原理与数学模型（20分） 实现原理为遗传算法原理： 按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选，使得适应度高的个体被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代。这样周而复始，群体中个体适应度不断提高，直到满足一定的条件。 数学模型如下： 设图G 由非空点集合12{,...}n V V V V = 和边集合12{,...}m E e e e = 组成，其中121221(,)e ,P ,)(P ,P ), i i i i i i i i e P P E P =∈≠且若（则G 为一个有向图； 又设i e 的值为i a ，12{,...},m A a a a = 故G 可表示为一个三元组{,,}G P E A = 则求最短路径的数学模型可以描述为：

甘特图实验报告doc

甘特图实验报告 篇一：Project实验报告 Project实验报告 朱曦朦 学号：XX306202412信管1001 实验目的： 通过做出一个标准的实验，了解project的基本运用方法和实验步骤，掌握设定项目的开始日期的基本方法。完成资源的优化配置，实现资源的充分利用。并对工期做一个初步的调整， 提高估计工期的精确度，掌握PERT的方法，实现整个过程(本文来自：https://www.wendangku.net/doc/9f5215328.html, 小草范文网:甘特图实验报告)的最优配置。对甘特图，关键路径等基本定义有一个初步的了解，初步学习到PROJECT的基本内容。 一；定义起始时间： 在定义项目中进行时间的确认： 一直保存至第三步，进行初始化的设定。 二复制新产品模板. 三调整资源的最大单位 修改资源“产品工程设计”的最大单位为200%，并增加资源“生产线”（工时资源，100%，用于完成生产任务，原来工程师需要5小时完成的任务，生产线只要1小时就能完

成，但必须同时配1名产品工程设计进行监控）。 通过视图进入资源工作表，将“产品工程设计”的最大单位改为 200% 在甘特图中未找到工程师，所以未对其进行修改。 三．为了提高估计工期的精确度，采用PERT技术规划项目工期（选取2到3个任务进行规划）。 设置PERT权重 设置后观察得到PERT项工作表。 选取2，3个项目后确定乐观工期，预期工期，悲观工期，通过计算PERT得出结论。 四．分析项目工期由哪些任务决定，确定压缩工期的方法。通过格式中的甘特图向导，对关键路径进行确认，从而得到确定项目工期的任务，由红线显示。编号为2，3，5，6，8，9，10， 11 对项目进行优化，可以通过2种路径，一是调整关键路径的工期，将其缩短。二是删除原有的链接关系，将后面的工期开始时间提前，如下图所示。 篇二：MS Project 上机实验报告 MS Project 上机实验报告 一、工程概况

《数据结构课程设计》最短路径问题实验报告

《数据结构课程设计》最短路径问题实验报告

目录 一、概述 0 二、系统分析 0 三、概要设计 (1) 四、详细设计 (5) 4.1建立图的存储结构 (5) 4.2单源最短路径 (6) 4.3任意一对顶点之间的最短路径 (7) 五、运行与测试 (8) 参考文献 (11) 附录 (12)

交通咨询系统设计（最短路径问题）一、概述 在交通网络日益发达的今天，针对人们关心的各种问题，利用计算机建立一个交通咨询系统。在系统中采用图来构造各个城市之间的联系，图中顶点表示城市，边表示各个城市之间的交通关系，所带权值为两个城市间的耗费。这个交通咨询系统可以回答旅客提出的各种问题，例如：如何选择一条路径使得从A城到B城途中中转次数最少；如何选择一条路径使得从A城到B城里程最短；如何选择一条路径使得从A城到B城花费最低等等的一系列问题。 二、系统分析 设计一个交通咨询系统，能咨询从任何一个城市顶点到另一城市顶点之间的最短路径(里程)、最低花费或是最少时间等问题。对于不同的咨询要求，可输入城市间的路程、所需时间或是所需费用等信息。 针对最短路径问题，在本系统中采用图的相关知识，以解决在实际情况中的最短路径问题，本系统中包括了建立图的存储结构、单源最短问题、对任意一对顶点间最短路径问题三个问题，这对以上几个问题采用了迪杰斯特拉算法和弗洛伊德算法。并未本系统设置一人性化的系统提示菜单，方便使用者的使用。

三、概要设计 可以将该系统大致分为三个部分： ①建立交通网络图的存储结构； ②解决单源最短路径问题； ③实现两个城市顶点之间的最短路径问题。

迪杰斯特拉算法流图：

project项目管理实验报告

计算机辅助项目管理 课程报告 班级： 学号： 姓名： 指导教师： 完成日期： -

目录 1、项目概况 (2) 1.1项目简介 (3) 1.2项目任务关系、固定成本及资源需求量 (2) 1.3可用资源 (2) 2、项目的实施计划 (3) 2.1初始计划 (3) 2.2初始计划的调整和优化 (5) 3、跟踪监控 3.1第一轮监控 (7) 3.2第二轮监控 (21) 3.3第三轮监控 (25) 3.4第四轮监控 (25) 4、项目完工总结分析报告 4.1总结分析报告 (26) 4.2分析实施和管理的成效 (26) 4.3目标实现措施的分析 (26) 5.学习思考总结 5.1问题思考 (27) 5.2问题分析与总结 (28) PROJECT项目管理课程报告

1、项目概况 1.1项目简介 项目的主要工作是维修某主要道路下一段长约1公里的供水管道，市政局要求电力部门配合施工，同时铺设一条地下电缆，以增加该道路两侧的用电用户。由于该项目是在现有道路上开挖，故市政局决定在回填后顺便铺设新的混凝土路面。为此，专门成立了一个项目管理办公室，以管理、协调该项目。项目内容包括：供水工程、电力工程和道路工程。整个项目从2016年7月1日提交预算报批为开始，市政局希望将项目施工对公众造成的影响降至最低，故希望该项目能在2016年10月底竣工并恢复交通。 1.2项目任务关系、固定成本及资源需求量 项目各项任务逻辑关系及固定成本(设备费、材料费等)、资源需求量如表1。 表1 工程工艺关系、固定成本及所需资源表 编号工序名称固定 成本 紧前 工序 资源需求 技工壮工 人数工日人数工日 1 道路及配套工程 2 准备工作 3 预算报批5000 4 对外公告1500 3 5 开走路上停留 的车辆 2000 4 3 6 6 开挖槽沟50000 5 15 200 7 供水工程5000 8 维修水管50000 6 12 200 35 500 9 压力试验1500 8 5 10 10 电力工程 11 支设新电杆15000 5 5 50 10 75 12 铺设电缆50000 6 8 50 25 150 13 吊装变压器75000 11,12,16 15 100 25 250 14 电力入户25000 13 20 240 20 240 15 道路工程25000 16 剪除树枝1500 5 6 12 17 复铺路面150000 9,12 20 300 30 420 18 恢复交通14,17 预算报批需1周，对外公告需2周时间。 1.3可用资源

分支限界法实现单源最短路径问题

实验五分支限界法实现单源最短路径 一实验题目：分支限界法实现单源最短路径问题 二实验要求：区分分支限界算法与回溯算法的区别，加深对分支限界法的理解。 三实验内容：解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。算法从图G的源顶点s和空优先队列开始。 结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。 四实验代码 #include using namespace std; const int size = 100; const int inf = 5000; //两点距离上界 const int n = 6; //图顶点个数加1 int prev[n]; //图的前驱顶点 int dist[] = {0,0,5000,5000,5000,5000}; //最短距离数组 int c[n][n] = {{0,0,0,0,0,0},{0,0,2,3,5000,5000}, //图的邻接矩阵 {0,5000,0,1,2,5000},{0,5000,5000,0,9,2}, {0,5000,5000,5000,0,2},{0,5000,5000,5000,5000,0}}; const int n = 5; //图顶点个数加1 int prev[n]; //图的前驱顶点 int dist[] = {0,0,5000,5000,5000}; int c[][n] = {{0,0,0,0,0},{0,0,2,3,5000},{0,5000,0,1,2},{0,5000,5000,0,9}, {0,5000,5000,5000,0}};

最短路径实验报告

一、实验目的 学习掌握图的存储结构 利用最短路径算法，通过java编程实现最短路径输出。 二、实验环境 Eclipse平台 三、实验过程 最短路径算法问题是计算机科学、运筹学、地理信息系统和交通诱导、导航系统等领域研究的一个热点。传统的最短路径算法主要有Floyd算法和Dijkstra算法。Floyd 算法用于计算所有结点之间的最短路径。Dijkstra算法则用于计算一个结点到其他所有结点的最短路径。本程序利用Dijkstra算法用java语言实现最短路径的可视化。 流程: 画无向邻接矩阵邻接矩阵初始化求取最短路径 Java文件如下 M ain.java 文件： import java.awt.BorderLayout; import java.awt.Color; import java.awt.FlowLayout; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import java.awt.event.ItemEvent; import java.awt.event.ItemListener; import java.util.StringTokenizer; import javax.swing.JButton; import javax.swing.JComboBox; import javax.swing.JFrame; import javax.swing.JLabel; import javax.swing.JPanel; import javax.swing.border.TitledBorder; public class Main { public static void main(String args[]) { new UI("最短路径"); } } @SuppressWarnings("serial") class UI extends JFrame implements ActionListener, ItemListener { JFrame frame; JButton button;

关键路径的查找实验报告

中国矿业大学矿业工程学院 实验报告 课程名称计算机软件设计基础 姓名 xxxx 班级采矿10-8班学号 xxxxx 日期 2012年10月 成绩教师 xxxx

3．2算法步骤：

(1)输入e条弧，建立AOE网的存储结构。 (2)从源点v1出发，令ve(1)=0,求ve(j)，2<=j<=n。 (3)从汇点vn出发，令vl(n)=ve(n),求vl(i) 1<=i<=n-1。 (4)根据各顶点的ve和vl值，求每条弧s（活动）的最早开始时间e(s)和最晚开始时间l(s)，其中e(s)=l(s)的为关键活动。 总结 首先，关于程序方面，我发现即使对设计思路有了眉目，知道了所要用到的数据结构、用邻接表来存储AOE-网、建立栈来求拓扑序列、输出的拓扑序列的个数少于节点数则有回路等等，要把这些方法写成函数代码，其实还是一件非常不容易的事情。再加上要完善设计思路，构造整个程序框架在内，都是一件工作量非常大的工作。 在处理程序代码的时候，有两个问题始终解决不了。一是程序输入时只能输入整形数据，而非整形的输入则会导致程序异常停止，但是因为整形的输入方式已贯穿整个程序，若要修改只能另外重做整个程序，所以暂不考虑修改，而打算做一个判错系统，判断若非整形的输入则报错；二是第一种错误的解决方案未能成功实行，于网路上搜索到了几种判断是否为整形数据的程序代码，但将其修改融合到求关键路径的程序中，虽然没有错误可以运行，但是却不能正确的报错。 于是，在尝试多种方案却仍不成功的前提下，我只好选择加上提示语，即：printf("请输入某项目的信息，并请用整形数字表示（格式：弧头，

单源最短路径 贪心算法

实验三单源最短路径 一、实验目的及要求 掌握贪心算法的基本思想 用c程序实现单源最短路径的算法 二、实验环境 Window下的vc 2010 三、实验内容 1、有向图与单源点最短路径 2、按路径长度非降的次序依次求各节点到源点的最短路径 3、Dijkstra算法 四、算法描述及实验步骤 设给定源点为Vs，S为已求得最短路径的终点集，开始时令S={Vs} 。当求得第一条最短路径(Vs ，Vi)后，S为{Vs，Vi} 。根据以下结论可求下一条最短路径。 设下一条最短路径终点为Vj ，则Vj只有：源点到终点有直接的弧 ；从Vs 出发到Vj 的这条最短路径所经过的所有中间顶点必定在S中。即只有这条最短路径的最后一条弧才是从S内某个顶点连接到S外的顶点Vj 。 若定义一个数组dist[n]，其每个dist[i]分量保存从Vs 出发中间只经过集合S中的顶点而到达Vi的所有路径中长度最小的路径长度值，则下一条最短路径的终点Vj必定是不在S中且值最小的顶点， 即：dist[i]=Min{ dist[k]| Vk∈V-S } 利用公式就可以依次找出下一条最短路径。 在程序中c[][]表示带权邻接矩阵， dist[]表示顶点到源点的最短路径， p[]记录顶点到源点最短路径的前驱节点， u源点，函数Way是递归的构造出最短路径的次序。 五、实验结果 程序执行的结果： 六、源代码 #include #include using namespace std;

#define MAX 999 void getdata(int **c,int n) { int i,j; int begin,end,weight; for (i=1;i<=n;i++) { for (j=1;j<=n;j++) { if(i==j) c[i][j]=0; else c[i][j]=MAX; } } do { cout<<"请输入起点终点权值(-1退出)："; cin>>begin; if(begin==-1) break; cin>>end>>weight; c[begin][end]=weight; } while(begin!=-1); } void Dijkstra(int n,int v ,int *dist,int *prev,int **c) { bool s[MAX]; int i,j; for (i=1;i<=n;i++) { dist[i]=c[v][i]; //从源点到各点的值 s[i]=false; if(dist[i]==MAX) prev[i]=0; //最大值没有路径 else prev[i]=v; //前驱为源点 } dist[v]=0;s[v]=true; for (i=1;i<=n;i++) { int temp=MAX; int u=v; for(j=1;j<=n;j++) if((!s[j])&&(dist[j]

最短路径实验报告

云南财经大学信息学院学生综合性与设计性实验报告 （2013—2014 学年第 2 学期） 周次：第7周日期：2014年 4 月 17 日地点： 一、实验内容与目的 1.内容 查看“最短路径.swf”，选择熟悉的程序设计语言定义有向图，根据动画演示求取从有向图任一结点到其他结点的最短路径。 2.实验目的 了解最短路径的概论，掌握求最短路径的方法。 二、实验原理或技术路线（可使用流程图描述） 实验原理：(李燕妮负责设计，周丽琼负责编程) 图是由结点的有穷集合V和边的集合E组成，求最短路径用迪杰斯特拉算法： 1)适用条件&范围： 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 1.取V-S中的一顶点u使得dis[u]=min{dis[v]|v∈V-S}

2.S=S+{u} 3.For V-S中每个顶点v do Relax(u,v,Wu,v) c)算法结束：dis[i]为s到i的最短距离；pre[i]为i的前驱节点 三、实验环境条件（使用的软件环境） Microsoft Visual C++6.0 四、实验方法、步骤（列出程序代码或操作过程） /*本程序的功能是求图中任意两点间的最短路径*/ #include #include #include #include #define ING 9999 typedef struct ArcCell{ int adj; /*顶点关系类型，用1表示相邻，0表示不相邻*/ }ArcCell,**AdjMatrix; /*邻接矩阵*/ typedef struct type{ char data[3]; /*顶点值*/ }VertexType; typedef struct{ VertexType *vexs; /*顶点向量*/ AdjMatrix arcs; /*邻接矩阵*/ int vexnum,arcnum; /*图的顶点数和边数*/ }MGraph; /*初始图*/ void InitGraph(MGraph *G) { int i,nu,mu; printf("\n输入顶点的个数和（边）弧的个数："); scanf("%d %d",&nu,&mu); G->arcs=(ArcCell **)malloc(nu*sizeof(ArcCell *)); for(i=0;iarcs[i]=(ArcCell *)malloc(nu*sizeof(ArcCell)); G->vexs=(VertexType *)malloc(nu*sizeof(VertexType)); /*分配顶点空间*/ G->vexnum=nu;G->arcnum=mu; /*图的顶点数和边数*/ }

Project实验报告

Project实验报告 朱曦朦 学号：2010306202412 信管1001 实验目的： 通过做出一个标准的实验，了解project的基本运用方法和实验步骤，掌握设定项目的开始日期的基本方法。完成资源的优化配置，实现资源的充分利用。并对工期做一个初步的调整， 提高估计工期的精确度，掌握PERT的方法，实现整个过程的最优配置。对甘特图，关键路径等基本定义有一个初步的了解，初步学习到PROJECT的基本内容。 一；定义起始时间：

在定义项目中进行时间的确认： 一直保存至第三步，进行初始化的设定。二复制新产品模板.

三调整资源的最大单位 修改资源“产品工程设计”的最大单位为200%，并增加资源“生产线”（工时资源，100%，用于完成生产任务，原来工程师需要5小时完成的任务，生产线只要1小时就能完成，但必须同时配1名产品工程设计进行监控）。 通过视图进入资源工作表，将“产品工程设计”的最大单位改为200% 在甘特图中未找到工程师，所以未对其进行修改。

三．为了提高估计工期的精确度，采用PERT技术规划项目工期（选取2到3个任务进行规划）。 设置PERT权重 设置后观察得到PERT项工作表。 选取2，3个项目后确定乐观工期，预期工期，悲观工期，通过计算PERT得出结论。

四．分析项目工期由哪些任务决定，确定压缩工期的方法。通过格式中的甘特图向导，对关键路径进行确认，从而得到确定项目工期的任务，由红线显 示。编号为2，3，5，6，8，9，10，11 的链接关系，将后面的工期开始时间提前，如下图所示。

实验总结： 通过按要求做实验，初步掌握的project的基本方法，但大部分还是按照书本的内容照搬，自己缺乏独立的融会贯通并将只是运用到实际甘特图中，并且，在有一些需要拓展的部分自己还是缺乏想法，没能很好地掌握知识。后面还需要多加练习，对制图还有一定的兴趣，但还是缺乏足够的训练。

单源最短路径问题

实验四单源最短路径问题 一、实验目的： 1、理解分支限界法的剪枝搜索策略； 2、掌握分支限界法的算法柜架； 3、掌握分支限界法的算法步骤； 4、通过应用范例学习动态规划算法的设计技巧与策略； 二、实验内容及要求： 1、使用分支限界法解决单源最短路径问题。 2、通过上机实验进行算法实现。 3、保存和打印出程序的运行结果，并结合程序进行分析，上交实验报告。 三、实验原理： 分支限界法的基本思想： 1、分支限界法与回溯法的不同： 1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。 2、分支限界法基本思想： 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。

此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 3、常见的两种分支限界法： 1）队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 2）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 四、程序代码 #include using namespace std; int matrix[100][100]; // 邻接矩阵 bool visited[100]; // 标记数组 int dist[100]; // 源点到顶点i的最短距离 int path[100]; // 记录最短路的路径 int source; // 源点 int vertex_num; // 顶点数 int edge_num; // 边数 int destination; // 终结点 void Dijkstra(int source) { memset(visited, 0, sizeof(visited)); // 初始化标记数组 visited[source] = true; for (int i = 0; i < vertex_num; i++) { dist[i] = matrix[source][i]; path[i] = source; } int min_cost; // 权值最小 int min_cost_index; // 权值最小的下标 for (int i = 1; i < vertex_num; i++) // 找到源点到另外 vertex_num-1 个点的最短路径{ min_cost = INT_MAX;

最短路径_Dijkstra算法__实验报告

实验六：编程实现Dijkstra 算法求最短路问题. 1.需求分析： 首先让用户输入一个带权的有向图，输入时可通过一对一对输入存在弧的两个弧头与弧尾顶点以及弧上的权值从而输入整个有向图。用户输入一对对弧后，我们可以采用数组的形式来进行存储每个顶点之间的权值，最后由用户输入该有向图的源点（即每个最短路径的起点），要求源点必须为刚才输入的各顶点中的某一个，如果用户输入错误，程序要给出错误信息提示并退出程序。然后，我们可以设计一个Graph这样的类，将对关系的各种操作放入其中，然后我们在主函数中调运这个类就可以实现最短路问题的求解了。 2.概要设计： ①.构造一个新的类Graph: class Graph { private: int arcs[MAX][MAX],Path[MAX][MAX],D[MAX]; int arcnum,vexnum,weight,v0; Type a,b,vexs[MAX]; public: void Creat_Graph(); void Show_ShortestPath(); void ShortestPath_DIJ(); }; ②.结构化调用类中方法的主函数： int main() { Graph G; G.Creat_Graph(); G.ShortestPath_DIJ(); G.Show_ShortestPath(); return 0; } 3.代码实现： #include #define MAX 100 #define INFINITY INT_MAX enum BOOL{FALSE,TRUE}; using namespace std; template class Graph {

网络计划实验报告

PERT 实验 商业中心建设活动持续时间表 活动紧前活动需要时间(周) A 设计－20 B 批准－10 C 招标A, B8 D 建设C24 E 外装修D8 F 谈判A,B14 G 签约F10 H 区域分割D, G6 I 内装修H12 J 进驻I, E6 正常正常加急加急最大成本/时间 时间成本时间成本减少比率 A*203012808 6.25 B101010100- C*8106162 3.0 D*24 230020 2340410.0 E8110 4 1204 2.5 F141210204 2.0 G1*******- H* 6202254 1.25 I* 12160101702 5.0 J*6106100- 根据以上表格给出的信息，用PERT软件画出项目网络计划图，并进行网络计算与优化设计。

网络计划方法: 大型项目的开发涉及很复杂的项目协调和管理问题，为使项目管理人员对项目进度有全面的了解，进行有效的控制，必须使用科学的管理方法；网络计划法是使用最广泛的方法之一，关键路径法(critical path method 缩写为CPM)和项目评审技术(program evaluation and review technique 缩写为PERT)是两种使用最广泛的网络计划技术。网络计划方法的优点使它适用于生产技术复杂，工作项目繁多，且紧密联系的一些跨部门的工作计划，如：新产品研制开发；大型工程项目建设；生产技术准备；复杂设备的大修计划。 网络计划方法的基本原理: 将工程项目分解为相对独立的活动，根据各活动先后顺序、相互关系以及完成所需时间做出反映项目全貌的网络图；从项目完成全过程着眼，找出影响项目进度的关键活动和关键路线，通过对资源的优化调度，实现对项目实施的有效控制和管理。 网络计划方法的主要功能: 1用网络图描述一个实际项目的管理问题 (画网络图)； 2计算项目的最早、最晚完成和开工时间 (网络计算)； 3寻找关键活动和关键路径(网络分析); 4根据以上分析对网络进行优化 PERT网络分析法 PERT网络分析法(计划评估和审查审技术，Program Evaluation and Review Technique) PERT(Program Evaluation and Review Technique)即计划评审技术，最早是由美国海军在计划和控制北极星导弹的研制时发展起来的。PERT技术使原先估计的研制北极星潜艇的时间缩短了两年。简单地说，PERT是利用网络分析制定计划以及对计划予以评价的技术，它能协调整个计划的各道工序，合理安排人力、物力、时间、资金，加速计划的完成。在现代计划的编制和分析手段上，PERT被广泛的使用，是现代化管理的重要手段和方法。 一．画网络图 画网络图应注意以下规则: 1、按工作本身的逻辑顺序连接箭线 2、网络图中不允许出现循环线路 3、在网络图中不允许出现代号相同的箭线 4、在一个网络图中只允许有一个起点节点，一般只允许出现一个终点节点（多目标网络图除外） 5、在网络图中不允许出现有双向箭头或无箭头的线段 6、网

实验四图的最短路径弗洛伊德算法实现

数据结构与算法课程实验报告实验四：图的相关算法应用 姓名：王连平 班级：09信科2班 学号：I09630221

实验四图的相关算法应用 一、实验内容 求有向网络中任意两点之间的最短路。 二、实验目的 掌握图和网络的定义，掌握图的邻接矩阵、邻接表和十字链表等存储表示。掌握图的深度和广度遍历算法，掌握求网络的最短路的标号法和floyd算法。 三、问题描述 对于下面一张若干个城市以及城市间距离的地图，从地图中所有可能的路径中求出任意两个城市间的最短距离及路径，给出任意两个城市间的最短距离值及途径的各个城市。 四、问题的实现 4.1数据结构的抽象数据类型定义和说明 1） typedef struct ArcCell{//储存弧信息 int Distance; ArcCell *info;//此项用来保存弧信息，，在本实验中没有相关信息要保存 }ArcCell,AdjMatrix[ MAX_VERTEX_NUM][ MAX_VERTEX_NUM]; typedef struct{//储存顶点信息 string vexs[ MAX_VERTEX_NUM];//顶点向量

AdjMatrix arcs;//邻接矩阵 int vexnum , arcnum;//图的当前顶点数和弧数 }MGraph; 顶点信息和弧信息都是用来建立一个有向网G 2） d[v][w];//G中各对顶点的带权长度 若P[v][w][u]为TRUE，则u是从v到w当前求得最短路径上的顶点 4.2主要的实现思路 首先通过一个函数（CreateDN）建立图的邻接矩阵储存方式,一次输入某条弧的起点，终点，和权值。通过调用Locate函数来找到该弧在邻接矩阵中的相应位置。 其次运用弗洛伊德算法来求各定点的最短路劲，具体思路为：如果从v到w有弧，则存在一条长度为arcs[v][w]的路径，该路径不一定是最短路径。考虑路径（v,u,w）是否存在，若存在，比较（v,w）和（v,u,w）的长度，取较短者为从v到w的中间点序号不大于0的最短路径。以此类推，每次增加一个点，从而求出任意两点间的最短路径。这样，经过n次比较后，所求得的必为从v到w的最短路径。按此方法，可以同时求得任意两点间的最短路径。 五、主要源程序代码（包含程序备注） #include #include using namespace std; #define INfinity 10000//最大值 # define MAX_VERTEX_NUM 10//最大顶点数 typedef struct ArcCell{//储存弧信息 int Distance; ArcCell *info; }ArcCell,AdjMatrix[ MAX_VERTEX_NUM][ MAX_VERTEX_NUM]; typedef struct{//储存顶点信息 string vexs[ MAX_VERTEX_NUM];//顶点向量 AdjMatrix arcs;//邻接矩阵 int vexnum , arcnum;//图的当前顶点数和弧数 }MGraph; int Locate(MGraph &G,string v) { int a=0; for (int i=0;i

PROJECT软件实验报告

PROJECT软件实验报告 成绩： 班级： 学号： 姓名： 2006年10月

实验一、项目基本设定与项目工作的安排与设定 一、实验目的 （1）通过实验使学生熟悉Microsoft Project2003的基本功能。 （2）对利用Microsoft Project2003创建项目及进行项目工作的安排与设定有一定掌握与认识。 二、实验内容 主要分为以下3部分： （1）Microsoft Project2003的基本介绍，主要包括：操作界面、常用视图、获得帮助。 （2）自选项目，利用Microsoft Project2003进行项目创建。 （3）利用Microsoft Project2003进行项目工作的安排与设定。包括在项目中建立任务、输入任务的工期、调整任务的层次、设定任务之间的关联性、在任务中加入更多说明。 三、实验步骤 （1）创建一个项目： （2）设置项目的基本信息： （3）日历的新建、日历的关联、日历的优先级、日历的共享： （4）输入任务： （5）周期性任务输入： （6）调整任务的层次关系 （7）显示WBS编码、定制WBS编码： （8）建立树状WBS； （9）输入与设定任务工期 （10）PERT分析； （11）建立任务的逻辑关系 （12）里程碑设定 （13）辅助功能设定（设定任务信息、设定备注信息） （14）任务拆分

实验二、项目资源与成本的分派与设定 一、实验目的 对利用Microsoft Project2003进行项目资源与成本的分派与设定有一定掌握与认识。 二、实验内容 主要分为以下3部分： （1）利用Microsoft Project2003建立项目所需资源。 （2）利用Microsoft Project2003将资源分派到任务中。 （3）利用Microsoft Project2003录入成本信息及查看成本。 三、实验步骤 （1）建立项目所需的资源（工时资源、材料资源）： （2）将资源分配到任务中： （3）成本信息录入： （4）查看任务的成本信息； （5）查看项目的总成本信息； （6）输入资源成本在过程中的变化信息； （7）固定成本的输入：