求如下有向图的关键路径以及任意两点之间的最短距离?
用CPM算法求有向图的关键路径和用Dijkstra算法求有向图的最短路径的C语言程序如下
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
#define MAX 20
#define INF 32767 // 此处修改最大值
#define nLENGTH(a) (sizeof(a)/sizeof(a[0]))
#define eLENGTH(a) (sizeof(a)/sizeof(char))/(sizeof(a[0])/sizeof(char))
typedef struct _graph{
char vexs[MAX]; // 顶点集合
int vexnum; // 顶点数
int edgnum; // 边数
int matrix[MAX][MAX]; // 邻接矩阵
}Graph, *PGraph;
// 边的结构体
typedef struct _EdgeData{
char start; // 边的起点
char end; // 边的终点
int weight; // 边的权重
}EData;
//指向节点的位置
int point_node(PGraph g,char c){
for(int i=0;i<g->vexnum;i++){
if(g->vexs[i]==c){
return i;
}
}
return -1;
}
PGraph create_graph(int b[][3],char a[],int n,int e){
char c1,c2; //边的2个顶点
PGraph g; //矩阵
g=(PGraph)malloc(sizeof(Graph));
//memset()第一个参数 是地址，第二个参数是开辟空间的初始值，第三个参数是开辟空间的大小
memset(g, 0, sizeof(Graph));
printf("顶点个数:
");//顶点数
g->vexnum=n;
printf("%d
",g->vexnum);
printf("边个数:
");//边数
g->edgnum=e;
printf("%d
",g->edgnum);
//初始化顶点
for(int j=0;j<g->vexnum;j++){
g->vexs[j]=a[j];
}
for(int i=0;i<g->edgnum;i++){
int p1,p2;
c1=char(b[i][0]);
c2=char(b[i][1]);
p1=point_node(g, c1);
p2=point_node(g, c2);
if (p1==-1 || p2==-1){
printf("input error: invalid edge!
");
free(g);
continue;
}
g->matrix[p1][p2]=b[i][2];
}
for(int i=0;i<g->vexnum;i++){
for(int j=0;j<g->vexnum;j++){
if(g->matrix[i][j]==0)
g->matrix[i][j]=INF;
}
}
return g;
}
//关键路径的最短时间
//关键路径法（Critical Path Method，CPM）
void CPM_road(PGraph g){
int i,j;
int a[MAX]={0},b[MAX]={-10};
int max=0;//最长路径
for( i=0;i<g->vexnum;i++){//列数遍历
for( j=0;j<g->vexnum;j++){//行数遍历
//如果g->matrix[j][i]大于0，说明此顶点有前顶点，由前边的遍历可知，前顶点的最长路径a[j]，
//加上g->matrix[j][i]的路径就是当前a[i]的路径
if(g->matrix[j][i]!=INF && g->matrix[j][i]+a[j]>max){
max=g->matrix[j][i]+a[j];
a[i]=max;
}
}
max=0;
}
//显示最长路径
printf("第一个顶点到每一个顶点的最长路径:");
printf("
");
for(i=0;i<g->vexnum;i++){
printf("V%d",i+1);
}
printf("
");
for(i=0;i<g->vexnum;i++){
printf("%d",a[i]);
}
printf("
");
printf("最后一个顶点到每个顶点的最长路径:");
for( i=g->vexnum-1;i>=0;i--){ //列数遍历
for( j=g->vexnum-1;j>=0;j--){ //行数遍历
//如果g->matrix[j][i]大于0，说明此顶点有前顶点，由前边的遍历可知，前顶点的最长路径a[j]，
//加上g->matrix[j][i]的路径就是当前a[i]的路径
if(g->matrix[i][j]!=INF && g->matrix[i][j]+b[j]>max){
max=g->matrix[i][j]+b[j];
b[i]=max;
}
}
max=0;
}
//显示最长路径
printf("
");
for(i=0;i<g->vexnum;i++){
printf("V%d",i+1);
}
printf("
");
for(i=0;i<g->vexnum;i++){
printf("%d",b[i]);
}
printf("
");
printf("关键路径:
");
for(i=0;i<g->vexnum;i++){
if(a[i]==a[g->vexnum-1]-b[i]){
printf("V%c",g->vexs[i]);
}
}
printf("
");
}
void print_shortest_path(PGraph g,int* distance,int* path,int* used,int start,int end){
// 输出最短距离并打印最短路径
int i = 0, pre, inverse_path[g->vexnum];
char s1[3],s2[3];
sprintf(s1, "V%d", (start+1));
sprintf(s2, "V%d", (end+1));
printf("从%s顶点到%s顶点的最短距离: %d
", s1, s2, distance[end]);
inverse_path[i] = end;
pre = path[end];
if(pre == -1){
printf("没有通路!
");
}else{
while(pre != start){
inverse_path[++i] = pre;
pre = path[pre];
}
inverse_path[++i] = start;
printf("从%s顶点到%s顶点的最短路径:
", s1, s2);
for(; i > 0; i--){
sprintf(s1, "V%d", (inverse_path[i]+1));
printf("%s -> ", s1);
}
sprintf(s1, "V%d", (inverse_path[i]+1));
printf("%s
", s1);
}
return;
}
void shortest_path(PGraph g,int start, int end){ // 基于Dijkstra算法的最短路径函数
int distance[g->vexnum]; // 用于存放起始点到其余各点的最短距离
int path[g->vexnum]; // 用于存放起始点到其余各点最短路径的前一个顶点
int used[g->vexnum] = { 0 }; // 用于标记该顶点是否已经找到最短路径
int i, j, min_node, min_dis, pass_flag = 0;
for(i = 0; i < g->vexnum; i++){
distance[i] = g->matrix[start][i]; // 初始化距离数组
if(g->matrix[start][i] < INF){
path[i] = start; // 初始化路径数组
}else{
path[i] = -1;
}
}
used[start] = 1;
path[start] = start;
for(i = 0; i < g->vexnum; i++){
min_dis = INF;
for(j = 0; j < g->vexnum; j++){
if(used[j] == 0 && distance[j] < min_dis){
min_node = j;
min_dis = distance[j];
pass_flag++; // 标记是否存在通路
}
}
if(pass_flag != 0){
used[min_node] = 1;
for(j = 0; j < g->vexnum; j++){
if(used[j] == 0){
if(g->matrix[min_node][j] < INF && distance[min_node] + g->matrix[min_node][j] < distance[j]){
distance[j] = distance[min_node] + g->matrix[min_node][j];
path[j] = min_node;
}
}
}
}
}
print_shortest_path(g,distance, path, used, start, end);
return;
}
int main(){
int i,j;
PGraph gp;
char a[]={'1', '2', '3', '4', '5', '6', '7'};
int b[][3]={{'1', '2',3},
{'1', '3',2},
{'1', '4',6},
{'2', '4',2},
{'2', '5',4},
{'3', '4',1},
{'3', '6',3},
{'4', '5',1},
{'5', '7',3},
{'6', '7',4}};
int n=nLENGTH(a);
int e=eLENGTH(b);
gp=create_graph(b,a,n,e);
//打印邻接矩阵
printf("邻接矩阵:
");
for (i = 0; i < gp->vexnum; i++){
for (j = 0; j < gp->vexnum; j++)
printf("%d ", gp->matrix[j][i]);
printf("
");
}
CPM_road(gp);
printf("
");
for(i=0;i<gp->vexnum;i++){
for(j=0;j<gp->vexnum;j++){
if(i!=j)
shortest_path(gp,i, j);
}
}
return 0;
}
运行结果
奚垂辰1135 :答：//如果g->matrix[j][i]大于0，说明此顶点有前顶点，由前边的遍历可知，前顶点的最长路径a[j]，//加上g->matrix[j][i]的路径就是当前a[i]的路径 if(g->matrix[j][i]!=INF && g->matrix[j][i]+a[j]>...
奚垂辰1135 :答：a1 a2 a4 a8 a9 所组成的路径即为关键路径 ：a1->a4->a9 和 a2->a8->a9
奚垂辰1135 :答：AOV网 ：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，就是AOV网。关键路径算法原理 ：先求所有顶点的事件最早发生时间（从起点开始计算），如有顶点1和顶点2...
奚垂辰1135 :答：求上图中VOE网中的关键路径：1，求事件的最早开始时间ve=max{顶点+边}和最晚开始时间vl=min{尾-边} 2，为了后面更好的求活动的最早开始时间和最晚开始时间，将ve和vl都在图中标识出来，ve用红笔，vl用黑笔 3，求...
奚垂辰1135 :答：关键路径的计算方法如下：（1） 输入e条弧<j,k>，建立AOE网的存储结构；（2） 从源点v1出发，令ve(1)=0，求 ve(j) ,2<=j<=n；（3） 从汇点vn出发，令vl(n)=ve(n)，求 vl(i), 1<=i<=n-1；（4...
奚垂辰1135 :答：根据各顶点的ve和vl值，求每条弧s（活动）的最早开始时间e(s)和最晚开始时间l(s)，其中e(s)=l(s)的为关键活动。求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径；只有缩短关键活动的工期才有可能缩短...
奚垂辰1135 :答：AOE网是一种用于表示工程的带权有向图，其中顶点代表事件，有向边代表活动，边上的权值表示活动的持续时间。关键路径是指完成整个工程所需的最短时间，这条路径被称为关键路径。关键路径上的活动被称为关键活动，只有缩短...
奚垂辰1135 :答：aoe网完成工程的最短时间是26天。一、在现代化管理中，人们常用有向图来描述和分析一项工程的计划和实施过程，一个工程常被分为多个小的子工程，这些子工程被称为活动（Activity)，在带权有向图中若以顶点表示事件，有向...
奚垂辰1135 :答：1．在有向图中选一个没有前驱的顶点且输出。2．从图中删除该顶点和以它为尾的弧。重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。3．什么是关键路径？例...
奚垂辰1135 :答：对一个有向无环图G进行拓扑排序，将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边∈E(G)，则u在线性序列中出现在v之前。这样的线性序列称为满足拓扑次序的序列。拓扑排序由某个集合上的一个偏序得到...
