实验1. 贪心法求解单源最短路径问题
实验内容
本实验要求基于算法设计与分析的一般过程（即待求解问题的描述、算法设计、算法描述、算法正确性证明、算法分析、算法实现与测试）。应用贪心策略求解有向带权图的单源最短路径问题。
实验目的
通过本次实验，掌握算法设计与分析的一般过程，以及每个步骤的基本方法。并应用贪心法求解单源最短路径问题。
环境要求
对于环境没有特别要求。对于算法实现，可以自由选择C, C++, Java，甚至于其他程序设计语言。
实验步骤
步骤1：理解问题，给出问题的描述。
步骤2：算法设计，包括策略与数据结构的选择
步骤3：描述算法。希望采用源代码以外的形式，如伪代码、流程图等；
步骤4：算法的正确性证明。需要这个环节，在理解的基础上对算法的正确性给予证明；
步骤5：算法复杂性分析，包括时间复杂性和空间复杂性；
步骤6：算法实现与测试。附上代码或以附件的形式提交，同时贴上算法运行结果截图;
步骤7：技术上、分析过程中等各种心得体会与备忘，需要言之有物。
说明：步骤1-6在“实验结果”一节中描述，步骤7在“实验总结”一节中描述。
实验结果
1.问题描述
给定一个有向带全图G=（V，E），其中每条边的权是一个非负实数。另外，给定V中的一个顶点，称为源点。现在要计算源点到所有其他各个顶点的最短路径长度，这里的路径长度是指路径上所有经过边的权值之和。这个问题通常称为单源最短路径问题。
2.（1)Dijkstra算法思想
按各个结点与源点之间路径长度的非减次序，生成源点到各个结点的最短路径的方法。
即先求出长度最短的一条路径，再参照它求出长度次短的一条路径。依此类推，直到从源点到其它各结点的最短路径全部求出为止。
1959年提出的，但当时并未发表。因为在那个年代，算法基本上不被当做一种科学研究的问题。
（2）Dijkstra算法设计
集合S与V-S的划分：假定源点为u。集合S中的结点到源点的最短路径的长度已经确定，集合V-S中所包含的结点到源点的最短路径的长度待定。
特殊路径：从源点出发只经过S中的结点到达V-S中的结点的路径。
贪心策略：选择特殊路径长度最短的路径，将其相连的V-S中的结点加入到集合S中。3、描述算法
Dijkstra算法的伪代码：
DIJKSTRA(G, w, s)
INITIALIZE-SINGLE-SOURCE(G, s)
S = Φ
Q = G.V //V-S中的结点按特殊路径长度非减排序
while Q ≠Φ
u = EXTRACT-MIN(Q)
S = S ∪{u}
for each v∈G.Adj[u]
RELAX(u, v, w)
4、Dijkstra算法的求解步骤：
步骤1：设计合适的数据结构。带权邻接矩阵C记录结点之间的权值，数组dist来记录从源点到其它顶点的最短路径长度，数组p来记录最短路径。u为源点；
步骤2：初始化。令集合S={u}，对于集合V-S中的所有顶点x，设置dist[x]=C[u][x]。如果顶点x与源点相邻，设置p[x]=u；否则，p[x]=-1；
步骤3：贪心选择结点。在集合V-S中依照贪心策略来寻找使得dist[x]具有最小值的顶点t，t就是集合V-S中距离源点u最近的顶点。
步骤4：更新集合S和V-S。将顶点t加入集合S中，同时更新集合V-S；
步骤5：判断算法是否结束。如果集合V-S为空，算法结束。否则，转步骤6；
步骤6：对相关结点做松弛处理。对集合V-S中的所有与顶点t相邻的顶点x，如dist[x]>dist[t]+C[t][x]，则dist[x]=dist[t]+C[t][x]并设置p[x]=t。转步骤3。
5、Dijkstra算法的正确性证明–贪心选择性质：
采用归纳法。当S={s, p}时，则除源结点s之外的所有结点中，结点p到源点s的距离最短。这是显然的。
假设当S={s, p1, …, pk}时，即k个结点p1, …, pk到源点s的距离最短。当S={s, p1, …, pk, pk+1}时，很显然结点pk+1到源点s的距离是最短的。需证明：此时结点p1, …, pk到源点s的距离仍然是最短的。用反证法假设当结点pk+1加入到S后，pi结点经由结点pk+1到源点s的距离更短，即d(s, pk+1) + d(pk+1, pi) < d(s, pi)，有d(s, pk+1) < d(s, pi) ，则结点pk+1
应比pi早被选择到S中，与假设相矛盾。证毕。
6、时间复杂性：
EXTRACT-MIN()的时间复杂性为O(logn)；
二重循环的执行次数为(n-1)+(n-2)+…+1 = n(n-1)/2，即时间复杂性为O(n2)。
所以，该算法的时间复杂性为O(n2)。
空间复杂性：
优先队列Q的大小为n-1；
所以，该算法的空间复杂性为O(n)。
7、算法实现与测试。
实验总结
Dijkstra算法采用贪心策略，按各个顶点与源点之间路径长度递增的次序，生成源点到各个顶点的最短路径方法。先求出长度最短的一条路径，在参照它求出长度次短的一条路径，以此类推，直到从源点到其他各个顶点的最短路径全部求出。
在构造带权邻接矩阵时候，二维数组在dijkstra算法里采用指针传递参数，结果求得的最短路径为ox652555等等，因为算法按照课本编写所以觉得没有错，就在输出部分困扰了很久，这样告诉我们学习不能生搬硬套，出问题不可怕，仔细分析问题来源并解决才是最重要的。在定义无穷大整数时，程序里是999，输入矩阵时变成10000，结果出来很大的数没有规律。在设置循环变量时，从0到n导致输入数组的时候出错，又写了输出语句还是弄不明白，小小的一个bug浪费了大量的时间，现在要好好的弥补编程知识。利用经典的算法知识可以解决现实生活中的许多问题，利用程序实现充满乐趣和挑战。
Dijkstra算法代码：
#include
using namespace std;
const int intmax=999;
void Dijkstra(int n,int u,int* dist,int* p,int **&c){
bool s[n];
for(int i=1;i<=n;i++){
dist[i]=c[u][i];
s[i]=false;
if(dist[i]==intmax)
p[i]=-1;
else
p[i]=u;
}
dist [u]=0;
s[u]=true;
for(int i=1;i<=n;i++){
int temp=intmax;
int t=u;
for(int j=1;j<=n;j++){
if((!s[j])&&(dist[j] { t=j; temp=dist[i]; } if(t==u) break; s[t]=true; for(j=1;j<=n;j++) if((!s[j])&&(c[t][j] if(dist[j]>(dist[t]+c[t][j])) { dist[j]=dist[t]+c[t][j]; p[j]=t; } } } } int main() { cout<<"输入顶点个数: "; cin>>n; int* dist=new int[n+1]; int* p=new int[n+1]; int** c=new int*[n+1]; for(int i=0;i { c[i]=new int[n+1]; } cout<<"输入邻接矩阵: "< for(int i=0;i { for(int j=0;j { cin>>c[i][j]; } } int u; cout<<"输入源点:"; cin>>u; Dijkstra(n,u,dist,p,c); for(int i=1;i { cout< } for(int i=1;i { cout<<"顶点"< } return 0; } /* 0 8 32 999 999 12 0 16 15 999 999 29 0 999 13 999 21 999 0 7 999 999 27 19 0 */ 实验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] 硕士生考查课程考试试卷 考试科目：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 = 则求最短路径的数学模型可以描述为： 实验五分支限界法实现单源最短路径 一实验题目：分支限界法实现单源最短路径问题 二实验要求：区分分支限界算法与回溯算法的区别，加深对分支限界法的理解。 三实验内容：解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。算法从图G的源顶点s和空优先队列开始。 结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。 四实验代码 #include 《数据结构课程设计》最短路径问题实验报告 目录 一、概述 0 二、系统分析 0 三、概要设计 (1) 四、详细设计 (5) 4.1建立图的存储结构 (5) 4.2单源最短路径 (6) 4.3任意一对顶点之间的最短路径 (7) 五、运行与测试 (8) 参考文献 (11) 附录 (12) 交通咨询系统设计（最短路径问题）一、概述 在交通网络日益发达的今天，针对人们关心的各种问题，利用计算机建立一个交通咨询系统。在系统中采用图来构造各个城市之间的联系，图中顶点表示城市，边表示各个城市之间的交通关系，所带权值为两个城市间的耗费。这个交通咨询系统可以回答旅客提出的各种问题，例如：如何选择一条路径使得从A城到B城途中中转次数最少；如何选择一条路径使得从A城到B城里程最短；如何选择一条路径使得从A城到B城花费最低等等的一系列问题。 二、系统分析 设计一个交通咨询系统，能咨询从任何一个城市顶点到另一城市顶点之间的最短路径(里程)、最低花费或是最少时间等问题。对于不同的咨询要求，可输入城市间的路程、所需时间或是所需费用等信息。 针对最短路径问题，在本系统中采用图的相关知识，以解决在实际情况中的最短路径问题，本系统中包括了建立图的存储结构、单源最短问题、对任意一对顶点间最短路径问题三个问题，这对以上几个问题采用了迪杰斯特拉算法和弗洛伊德算法。并未本系统设置一人性化的系统提示菜单，方便使用者的使用。 三、概要设计 可以将该系统大致分为三个部分： ①建立交通网络图的存储结构； ②解决单源最短路径问题； ③实现两个城市顶点之间的最短路径问题。 迪杰斯特拉算法流图： 实验三单源最短路径 一、实验目的及要求 掌握贪心算法的基本思想 用c程序实现单源最短路径的算法 二、实验环境 Window下的vc 2010 三、实验内容 1、有向图与单源点最短路径 2、按路径长度非降的次序依次求各节点到源点的最短路径 3、Dijkstra算法 四、算法描述及实验步骤 设给定源点为Vs，S为已求得最短路径的终点集，开始时令S={Vs} 。当求得第一条最短路径(Vs ，Vi)后，S为{Vs，Vi} 。根据以下结论可求下一条最短路径。 设下一条最短路径终点为Vj ，则Vj只有：源点到终点有直接的弧 #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] 一、实验目的 学习掌握图的存储结构 利用最短路径算法，通过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; 实验四单源最短路径问题 一、实验目的： 1、理解分支限界法的剪枝搜索策略； 2、掌握分支限界法的算法柜架； 3、掌握分支限界法的算法步骤； 4、通过应用范例学习动态规划算法的设计技巧与策略； 二、实验内容及要求： 1、使用分支限界法解决单源最短路径问题。 2、通过上机实验进行算法实现。 3、保存和打印出程序的运行结果，并结合程序进行分析，上交实验报告。 三、实验原理： 分支限界法的基本思想： 1、分支限界法与回溯法的不同： 1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。 2、分支限界法基本思想： 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 3、常见的两种分支限界法： 1）队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 2）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 四、程序代码 #include 云南财经大学信息学院学生综合性与设计性实验报告 （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 单源最短路径的Dijkstra算法： 问题描述： 给定一个带权有向图G=（V，E），其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。 算法描述： Dijkstra算法是解单源最短路径的一个贪心算法。基本思想是：设置顶点集合S并不断地做贪心选择来扩充这个集合。一个顶点属于S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist做必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。 源代码： #include using namespace std; //-------------------------------------数据声明------------------------------------------------//c[i][j]表示边(i,j)的权 //dist[i]表示当前从源到顶点i的最短特殊路径长度 //prev[i]记录从源到顶点i的最短路径上的i的前一个顶点 //--------------------------------------------------------------------------------------------- void Dijkstra(int n, int v, int dist[], int prev[], int c[][LEN]) { bool s[LEN]; // 判断是否已存入该点到S集合中 for (int i = 1; i <= n; i++) { dist[i] = c[v][i]; s[i] = false; //初始都未用过该点 if (dist[i] == MAX) prev[i] = 0; //表示v到i前一顶点不存在 else prev[i] = v; } dist[v] = 0; s[v] = true; 实验六：编程实现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 数据结构与算法课程实验报告实验四：图的相关算法应用 姓名：王连平 班级：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 单源最短路径问题 I 用贪心算法求解 贪心算法是一种经典的算法，通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。一般具有2个重要的性质：贪心选择性质和最优子结构性质。 一、问题描述与分析 单源最短路径问题是一个经典问题，给定带权有向图G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。 分析过程：运用Dijkstra算法来解决单源最短路径问题。 具备贪心选择性质 具有最优子结构性质 计算复杂性 二、算法设计（或算法步骤） 用贪心算法解单源最短路径问题： 1.算法思想： 设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。 2.算法步骤： (1) 用带权的邻接矩阵c来表示带权有向图, c[i][j]表示弧 东华大学计算机学院离散数学 实验五：最短路径 实验所属系列：离散数学课后实验 实验对象：本科 相关课程及专业：离散数学，计算机专业 实验类型：课后实验 实验时数（学分）：4学时 实验目的 学习图的最短路径算法的实现。 实验内容与要求 根据输入的图形（实验四），输入起点和终点，求出最短路径和最短路径的长度。 实验的软硬件环境 PC机一台，装有VC++6.0或其它C语言集成开发环境。 实验准备 熟悉最短路径算法。 实验步骤 1．编写一段代码，接收键盘的输入定点的数量，并以输入的整数对作为边来建立图形的邻接矩阵（无向权重图）。 例如：5，6，12 表示定点5和定点6间有边，边的权重为12。 2 打印出邻接矩阵。 3．输入起点和终点。 4、打印最短路径和最短路径的长 #include 单源最短路径问题 所谓单源最短路径问题是指：已知图G＝（V，E），我们希望找出从某给定的源结点S∈V 到V中的每个结点的最短路径。 首先，我们可以发现有这样一个事实：如果P是G中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。 对于图G，如果所有Wij≥0的情形下，目前公认的最好的方法是由Dijkstra于1959年提出来的。 Dijkstra算法基本思想：设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。 （1）初始时，S中仅含有源节点。 （2）设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，用数组D[i]记录顶点i当前所对应的最短特殊路径长度。 （3）Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组D作必要的修改。 （4）一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。源程序1： //Dijkstra算法 #include 目录 交通咨询系统设计（最短路径问题）一、概述 在交通网络日益发达的今天，针对人们关心的各种问题，利用计算机建立一个交通咨询系统。在系统中采用图来构造各个城市之间的联系，图中顶点表示城市，边表示各个城市之间的交通关系，所带权值为两个城市间的耗费。这个交通咨询系统可以回答旅客提出的各种问题，例如：如何选择一条路径使得从A城到B城途中中转次数最少；如何选择一条路径使得从A城到B城里程最短；如何选择一条路径使得从A城到B城花费最低等等的一系列问题。 二、系统分析 设计一个交通咨询系统，能咨询从任何一个城市顶点到另一城市顶点之间的最短路径(里程)、最低花费或是最少时间等问题。对于不同的咨询要求，可输入城市间的路程、所需时间或是所需费用等信息。 针对最短路径问题，在本系统中采用图的相关知识，以解决在实际情况中的最短路径问题，本系统中包括了建立图的存储结构、单源最短问题、对任意一对顶点间最短路径问题三个问题，这对以上几个问题采用了迪杰斯特拉算法和弗洛伊德算法。并未本系统设置一人性化的系统提示菜单，方便使用者的使用。 三、概要设计 可以将该系统大致分为三个部分： ① 建立交通网络图的存储结构； ② 解决单源最短路径问题； ③ 实现两个城市顶点之间的最短路径问题。 四、详细设计 建立图的存储结构 定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设G=(V,E)是具有n个顶点的图，则G的邻接矩阵是具有如下定义的n阶方阵。 注：一个图的邻接矩阵表示是唯一的！其表示需要用一个二维数组存储顶点之间相邻关系的邻接矩阵并且还需要用一个具有n个元素的一维数组来存储顶点信息（下标为i的元素存储顶点 V的信 i 息）。 邻接矩阵的存储结构： 单源最短路径实验报告 实验题目：单元最短路径 实验目的：给定带权图G和源点V，求从V到G中其余各顶点的最短路径。 实验内容： 一、输入及结果： 输入：带全图G的各个顶点及各边的权值 输出：Dijkstra算法每一步的结果 二、算法描述 （1）关于单源最短路径 1．记S为已经找到的从V0出发的最短路径的中点的集合，它的初始状态为空集。那么，从V出发到图上其余各顶点VI可能达到的最短路径的初始值为 D[i]=arcs[Locate Vex(G,V)][i]. 2．选择Vj使得： D[j]=Min{D[i] | vi不属于S} Vj就是当前求得的一条从V出发的最短路径的终点。 将j加入到S中。 3．修改从V出发到集合V—S上任意顶点Vk可达到的最短路径长度。如果：D[j]+arcs[j][k] 目录 一、概述 0 二、系统分析 0 三、概要设计 (1) 四、详细设计 (4) 建立图的存储结构 (4) 单源最短路径 (5) 任意一对顶点之间的最短路径 (5) 五、运行与测试 (5) 参考文献 (7) 附录 (8) 交通咨询系统设计（最短路径问题）一、概述 在交通网络日益发达的今天，针对人们关心的各种问题，利用计算机建立一个交通咨询系统。在系统中采用图来构造各个城市之间的联系，图中顶点表示城市，边表示各个城市之间的交通关系，所带权值为两个城市间的耗费。这个交通咨询系统可以回答旅客提出的各种问题，例如：如何选择一条路径使得从A城到B城途中中转次数最少；如何选择一条路径使得从A城到B城里程最短；如何选择一条路径使得从A城到B城花费最低等等的一系列问题。 二、系统分析 设计一个交通咨询系统，能咨询从任何一个城市顶点到另一城市顶点之间的最短路径(里程)、最低花费或是最少时间等问题。对于不同的咨询要求，可输入城市间的路程、所需时间或是所需费用等信息。 针对最短路径问题，在本系统中采用图的相关知识，以解决在实际情况中的最短路径问题，本系统中包括了建立图的存储结构、单源最短问题、对任意一对顶点间最短路径问题三个问题，这对以上几个问题采用了迪杰斯特拉算法和弗洛伊德算法。并未本系统设置一人性化的系统提示菜单，方便使用者的使用。 三、概要设计 可以将该系统大致分为三个部分： ①建立交通网络图的存储结构； ②解决单源最短路径问题； ③实现两个城市顶点之间的最短路径问题。 迪杰斯特拉算法流图： 弗洛伊德算法流图： 四、详细设计 建立图的存储结构 定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设G=(V,E)是具有n 个顶点的图，则G 的邻接矩阵是具有如下定义的n 阶方阵。 ?? ???∞>∈<=，其他情况或或，若0E(G)V ,V )V ,(V ],[j i j i ij W j i A 注：一个图的邻接矩阵表示是唯一的！其表示需要用一个二维数组存储顶点之间相邻关系的邻接矩阵并且还需要用一个具有n 个元素的一维数组来存储顶点信息（下标为i 的元素存储顶点i V 的信息）。 邻接矩阵的存储结构： #define MVNum 100 单源最短路径 计科一班李振华 2012040711 1、问题描述 给定带权有向图G=（V，E），其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到其他所有顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。 2、问题分析 推导过程（最优子结构证明，最优值递归定义） 1、贪心算法 对于图G，如果所有Wij≥0的情形下，目前公认的最好的方法是由Dijkstra 于1959年提出来的。 已知如下图所示的单行线交通网，每弧旁的数字表示通过这条单行线所需要的费用，现在某人要从v1出发，通过这个交通网到v8去，求使总费用最小的旅行路线。 Dijkstra方法的基本思想是从vs出发，逐步地向外探寻最短路。执行过程中，与每个点对应，记录下一个数(称为这个点的标号)，它或者表示从vs 到该点的最短路的权(称为P标号)、或者是从vs到该点的最短路的权的上界(称为T标号)，方法的每一步是去修改T标号，并且把某一个具T标号的改变为具 P标号的点，从而使G中具P标号的顶点数多一个，这样至多经过n-1(n为图G的顶点数)步，就可以求出从vs到各点的最短路。 在叙述Dijkstra方法的具体步骤之前，说明一下这个方法的基本思想。s=1。因为所有Wij≥0，故有d(v1, v1)=0。这时，v1是具P标号的点。现在考察从v1发出的三条弧，(v1, v2), (v1, v3)和(v1, v4)。 （1）如果某人从v1出发沿(v1, v2)到达v2，这时需要d(v1, v1)+w12=6单位的费用； （2）如果他从v1出发沿(v1, v3)到达v3，这时需要d(v1, v1)+w13=3单位的费用； （3）若沿(v1, v4)到达v4，这时需要d(v1, v1)+w14=1单位的费用。 因为min{ d(v1, v1)+w12，d(v1, v1)+w13，d(v1, v1)+w14}= d(v1, v1)+w14=1，可以断言，他从v1到v4所需要的最小费用必定是1单位，即从v1到v4的最短路是(v1, v4)，d(v1, v4)=1。这是因为从v1到v4的任一条路P，如果不是(v1, v4)，则必是先从v1沿(v1, v2)到达v2，或者沿(v1, v3)到达v3。但如上所说，这时他已需要6单位或3单位的费用，不管他如何再从v2或从v3到达v4，所需要的总费用都不会比1小(因为所有wij≥0)。因而推知d(v1, v4)=1，这样就可以使v4变成具P标号的点。 （4）现在考察从v1及v4指向其余点的弧，由上已知，从v1出发，分别沿(v1, v2)、(v1, v3)到达v2, v3，需要的费用分别为6与3，而从v4出发沿(v4, v6)到达v6所需的费用是d(v1, v4)+w46=1+10=11单位。因min{ d(v1, v1)+w12，d(v1, v1)+w13，d(v1, v4)+w46}= d(v1, v1)+w13=3。基于同样的理由可以断言，从v1实验三 最短路径的算法(离散数学实验报告)
MATLAB实验报告,遗传算法解最短路径以及函数最小值问题讲解
分支限界法实现单源最短路径问题
《数据结构课程设计》最短路径问题实验报告
单源最短路径 贪心算法
最短路径实验报告
单源最短路径问题
最短路径实验报告
单源最短路径的Dijkstra算法
最短路径_Dijkstra算法__实验报告
实验四图的最短路径弗洛伊德算法实现
单源最短路径
最短路径算法实验报告
单源最短路径问题-Dijkstra
数据结构课程设计最短路径问题实验报告
单元最短路径,Dijkstra算法 实验报告
《数据结构课程设计》最短路径问题实验报告
单源最短路径(两种方法)
相关主题
文本预览