实验一:单源点最短路径
一、实验目的
设计一个 C 程序,实现求解单源点最短路径问题。
二、实验要求
本实验要求输出最短路径值以及最短路径
三、实验内容与原理
单源点最短路径问题,即,已知一个 n 结点有向图 G=(V,E)和边的权函
数 c(e),求由某指定结点 V0 到其他各个结点的最短路径,这里还假定所有的
权都是正的。
为了制定产生最短路径的贪心算法,对于这个问题应该想出一个多级解决办
法和一种最优的量度标准。方法之一是逐条构造这些最短路径,可以使用迄今已
生成的所有路径长度之和作为一种量度,为了使这一量度达到最小,其单独的每
一条路径都必须具有最小长度。使用这一量度标准时,假定已经构造了 i 条最短
路径,则下面要构造的路径应该是下一条最短的最小长度路径。首先,生成从 V0
到所有其它结点的最短路径。然后生成一条到第二近结点的最短路径等等。
四、算法及程序说明
本算法使用贪心法设计,生成从 v0 到所有其它结点的最短路径的贪心方
法就是按照路径长度的非降次序生成这些路径。
本程序运行图中输入的课本 P86 页图 3.10 所对应的成本邻接矩阵。单源点
选择的是 V0 点。最终的结果如图 1-1 所示。
五、源程序
/*单源点最短路径*/
#include<stdio.h>
int search(int*,int,int,int*);
main(){ /*生成单源点最短路径的贪心算法*/