}
if(m>t) {
j[t1].p=j1[i].p; j[t1].d=j1[i].d; }
t=t1; }else t1--; }
printf(\输出得到的结果：效益值,截止期限\ printf(\ for(i=1;i<=t;i++) {
printf(\ printf(\ } }
运行结果如下图所示：(运行结果与理论结果一致)
五、结果分析
将待作业的信息直接放入程序中，并显示。运行源程序后，直接得到可行解的效益值与截止期限。不难看出，运行结果与理论值一致。
设s是最终计入J中的作业数，则算法JS所需要的总时间是O(sn)。s≤n，故 最坏情况：TJS = О(n2)，特例情况：pi=di=n-i+1,1≤i≤n； 最好情况：TJS = О(n)，特例情况：di=i,1≤i≤n。
16
上机实验五
一、实验题目
贪心方法求单源点的最短路径问题
二、算法介绍
1、限定有向图中所有的权都是正的；
2、逐条构造所求最短路径，量度标准是使用迄今已生成的所有路径长度之和，单独的每一条路径都必须具有最小长度，按照路径长度的非降次序生成从源点（起始结点）到所有其它结点的最短路径。
三、程序流程图
说明：集合S表示对其已经生成了最短路径的那些结点（包括起始结点V0）的集合； cost[][]（是全局变量）中存放各结点之间的直接距离并规定无穷大为1024，表示两结点之间不可直达，cost[i][i]表示结点Vi与Vi的距离，规定其值为0。
四、源程序及实验结果
程序代码如下： #include
/*二维数组cost[6][6]存放的是一个有向图中各个结点的直接距离，其中从i到j不能直接到 达时它们的距离为无穷大，用1024表示 */
int cost[6][6]={ {0,50,10,1024,45,1024}, {1024,0,15,1024,10,1024}, {20,1024,0,15,1024,1024}, {1024,20,1024,0,35,1024}, {1024,1024,1024,30,0,1024}, {1024,1024,1024,3,1024,0}};
int min(int a,int b) //求a与b的最小值并返回该值 { if(a>b)a=b; return a; }
void shortest_paths(int v) { int u,num,i,w,tmin;
int dist[6]; //数组dist[i]中存放的是起始节点v与结点Vi的路径长度
int S[6]; //S[i]是结点Vi加入集合S的情况，不在S中时为0，在时为1 int n=6;
for(i=0;i dist[i]=cost[v][i]; 17 } printf(\输出v到所有结点的直接距离：\\n\ for(i=0;i S[v]=1; //将起始结点v加入集合S中 dist[v]=0; //结点v到v的路径长度为0 for(num=1;num<=n-1;num++) //确定由结点v出发的n-1条路 { i=0; while(S[i]==1) //找到一个不在集合S中的结点 { i++; } tmin=i; //tmin存放的是dist[i]值最小的结点下标i,默认初值为前面找到的 不在集合S中的结点的下标 for(i=0;i if(S[i]==1)continue; else if(dist[i] u=tmin; //将不在集合S中且dist[i]值最小的结点的下标记入u中 S[u]=1; //将结点Vtmin记入集合S中 for(w=0;w dist[w]=min(dist[w],dist[u]+cost[u][w]); } } printf(\输出所有结点加入集合S[]的情况:\\n\ for(i=0;i { printf(\ } printf(\分别输出v与各结点的最短路径长度:\\n\ for(i=0;i { printf(\ } printf(\} void main() { int v; char c; 18 do { c=getchar(); //输入起始结点的下标值 v=c-'0'; if(v>=0&&v<6) //当所输下标合法时求从该结点到所有结点（包括该结点）的路径长度 { shortest_paths(v); c=getchar(); } else break; //当所输下标不合法时结束 }while(c=='\\n'); } 运行结果如下：(运行结果与理论结果一致) 五、结果分析 运行源程序后，输入起始结点v的下标，回车，就会输出v到所有结点的直接距离，以及各结点加入集合S的情况，和v到各结点的最短路径长度。不难看出，运行结果与理论值一致。 由于任何一条边都有可能是最短路径中的边，所以求任何最短路径的算法都必须至少检查图中的每条边一次，所以这样的算法的最小时间是О(e)。 上机实验六 一、实验题目 动态规划求有向图最短路径 二、算法介绍 考察i到j的最短路径：首先确定哪个节点是该路径上具有最大编号的中间结点k，计算由i、j分别到k的最短路径，这2条路径都不可能有比k-1还大的中间节点。求解递推；用Ak（i，j）表示从i到j且不经过比k还大的结点的最短路径长度，由于G中不存在比n 19 还大的结点，因此A（i，j）=An（i，j），即由i到j的最短路径上不通过比n标号还大的结点。这条路径可能通过结点n也可能不通过节点n，如果通过结点n则An（i，j）=An-1（i，n）+An-1（n，j），如果不通过结点n，则An（i，j）=An-1（i，j）。组合起来得到 An（i，j）=min{An-1（i，j），An-1（i，n）+An-1（n，j）} 同理Ak（i，j）=min{Ak-1（i，j），Ak-1（i，k）+Ak-1（k，j）}，k》1. 简单的描述最短路径算法如下： I 从某一点k开始，根据cost[n][n]（比较A(i,j)与A(i,k)+A(k,j)的大小）修改从i到j的最短路径值，若A(i,k)+A(k,j) II. 重复1直到所有点均考虑完。 三、程序流程图 四、源程序及实验结果 #include #define INIFITY 1000 struct { int vexnum;//结点个数 int arcs[N][N];//邻接矩阵 }G;//图 void output (int a[N][N]) { int i, j;//循环参数 for (i=1; i 20