关键路径的基于P矩阵的算法程序实现
算法步骤：
(1)构造图G的P邻接矩阵M1（M的一次幂）；
(2)构造M；
(3)删去M1中除去第一行之外的所有行得到的矩阵仍然记为M1 ；
(4)构造秩为k的基本P矩阵Mk(M的k次幂）（k=2，…,n-1）且只保留各顶点之间的最长路径项；
(5)计算W且只保留源点到汇点的最长路径项；
(6)输出所有关键路径。
本人学习C++时间不长，对以上算法不是很清楚，不知如何编写程序。希望熟悉这种算法的高手指点，谢谢-。-
[解决办法]
#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX_VERTEX_NUM 30 //图的最大顶点数#define MAX 30 //栈的最大容量#define INFINITY 30000; //定义最大的最迟发生时间enum BOOL {False,True};typedef struct ArcNode{int adjvex; //该弧所指向的顶点的位置 int weight; //该弧所代表的活动的持续时间 struct ArcNode *nextarc; //指向下一条弧的指针}ArcNode; //弧结点typedef struct{int indegree[MAX_VERTEX_NUM]; //存放各顶点的入度 ArcNode* AdjList[MAX_VERTEX_NUM]; //指向第一条依附该顶点的弧的指针 int vexnum,arcnum; //图的当前顶点和弧数}Graph;typedef struct //定义堆栈结构{int elem[MAX]; //栈区 int top; //栈顶指针}Stack;int ve[MAX_VERTEX_NUM]; //全局变量，存放各顶点的最早发生时间void CreateGraph(Graph &); //生成图的邻接表BOOL CriticalPath(Graph); //求图的关键路径BOOL TopologicalSort(Graph,Stack &T); //进行拓扑排序void FindInDegree(Graph&); //求图各顶点的入度void Initial(Stack &); //初始化一个堆栈BOOL Push(Stack &,int); //将一个元素入栈BOOL Pop(Stack&,int &); //将一个元素出栈BOOL Gettop(Stack,int&); //得到栈顶元素BOOL StackEmpty(Stack); //判断堆栈是否为空void main(){Graph G; //采用邻接表结构的图 char j='y'; BOOL temp; //------------------程序解说---------------------------- printf("本程序将演示构造图的关键路径.\n"); printf("首先输入图的顶点数和弧数.\n格式：顶点数，弧数；例如:6,8\n"); printf("接着输入各弧(弧尾,弧头)和权值.\n格式：弧尾，弧头，权值；例如:\n1,2,3\n1,3,2\n"); printf("2,5,3\n5,6,1\n2,4,2\n4,6,2\n3,4,4\n3,6,3\n"); printf("程序将会构造该图并找出其关键路径.\n"); printf("关键路径:\n1->3 2\n3->4 4\n4->5 2\n"); //------------------------------------------------------ while(j!='N'&&j!='n') {CreateGraph(G); //生成邻接表结构的图 temp=CriticalPath(G); //寻找G的关键路径 if(temp==False) printf("该图有回路!\n"); //若返回为False,表明该图存在有环路 else printf("该图没有回路!\n"); printf("关键路径演示完毕，继续进行吗?(Y/N)"); scanf(" %c",&j); }}BOOL CriticalPath(Graph G){//G为有向网，输出G的各项关键活动 int j,dut,k,ee,el; int vl[MAX_VERTEX_NUM]; //存放各顶点的最迟发生时间 Stack T; //堆栈T存放拓扑排序的顶点序列 ArcNode*p; Initial(T); //初始化堆栈T if(!TopologicalSort(G,T)) return False; //利用拓扑排序求出各顶点的最早发生时间，并用T返回拓扑序列， //若返回False，表明该网有回路 printf("Critical Path:\n"); Gettop(T,k); //k取得拓扑序列的最后一个顶点，即该网的汇点 vl[k]=ve[k]; //汇点的vl=ve for(j=1;j<=G.vexnum;j++) if(j!=k) vl[j]=INFINITY; //将其他的顶点的vl置为IFINITY while(!StackEmpty(T)) //按拓扑逆序求各顶点的vl值 {Pop(T,j); for(p=G.AdjList[j];p;p=p->nextarc) {k=p->adjvex; dut=p->weight; if(vl[k]-dut<vl[j]) vl[j]=vl[k]-dut; //vl的求法：vl(i)=Min{vl(j)-dut(<i,j>)} <i,j>∈S,i=n-2,...0 } } for(j=1;j<=G.vexnum;j++) //求每条弧的最早开始时间ee和最迟开始时间el for(p=G.AdjList[j];p;p=p->nextarc) {k=p->adjvex; dut=p->weight; ee=ve[j]; el=vl[k]-dut; if(ee==el) printf("%d->%d%5d\n",j,k,dut); //若ee=el，则该弧为关键活动 } return True;}void CreateGraph(Graph &G){//构造邻接表结构的图G int i; int start,end,arcweight; ArcNode *s; printf("请输入顶点数和弧数(顶点数，弧数):"); scanf("%d,%d",&G.vexnum,&G.arcnum); //输入图的顶点数和弧数 for(i=1;i<=G.vexnum;i++) G.AdjList[i]=NULL; //初始化指针数组 printf("请输入各弧和权值，格式:弧尾,弧头,权值\n"); for(i=1;i<=G.arcnum;i++) {scanf("%d,%d,%d",&start,&end,&arcweight); //输入弧的起点和终点即该弧所代表的活动的持续时间 s=(ArcNode *)malloc(sizeof(ArcNode)); //生成一个弧结点 s->nextarc=G.AdjList[start]; //插入到邻接表中 s->adjvex=end; s->weight=arcweight; G.AdjList[start]=s; }}BOOL TopologicalSort(Graph G,Stack &T){//有向网G采用邻接表存储结构，求各顶点事件的最早发生时间ve， //T为拓扑序列顶点栈，S为零入度顶点栈。 //若G无回路，则用栈返回G的一个拓扑序列，且函数返回True,否则返回False int i,k; int count; //计数器 ArcNode* p; Stack S; FindInDegree(G); //求出图中各顶点的入度 Initial(S); //堆栈初始化，存放入度为零的顶点 for(i=1;i<=G.vexnum;i++) if(!G.indegree[i]) Push(S,i); //入度为零的顶点入栈 count=0; //对输出顶点记数 for(i=1;i<=G.vexnum;i++) ve[i]=0; //ve初始化 while(!StackEmpty(S)) {Pop(S,i); //i号顶点出S栈并入T栈，count记数 Push(T,i); count++; for(p=G.AdjList[i];p;p=p->nextarc) {k=p->adjvex; //对i号顶点的每个邻接顶点的入度减一 if(!(--G.indegree[k])) Push(S,k); //若入度为零，入栈 if((ve[i]+p->weight)>ve[k]) ve[k]=ve[i]+p->weight; //修改k号顶点的最迟发生时间 //ve的求法：ve(j)=Max{ve(i)+dut(<i,j>)} <i,j>∈S,j=1,2,…,n-1 } } if(count<G.vexnum) return False; //如输出顶点数少于图中顶点数，则该图有回路 else return True;}void FindInDegree(Graph &G){//求出图G的各顶点的入度，存放在G.indegree[1..G.vexnum]中 int i; ArcNode* p; for(i=1;i<=G.vexnum;i++) G.indegree[i]=0; for(i=1;i<=G.vexnum;i++) { for(p=G.AdjList[i];p;p=p->nextarc) G.indegree[p->adjvex]++; //弧头顶点的入度加一 }}void Initial(Stack &S){S.top=-1; //栈顶指针初始化为-1}BOOL Push(Stack &S,int ch){//将元素ch入栈，成功返回True,失败返回False if(S.top>=MAX-1) return False;//判断是否栈满 else {S.top++; //栈顶指针top加一 S.elem[S.top]=ch; //入栈 return True; }}BOOL Pop(Stack &S,int &ch){//将栈顶元素出栈,成功返回True，并用ch返回该元素值，失败返回False if(S.top<=-1) return False;//判断是否栈空 else {S.top--; //栈顶指针减一 ch=S.elem[S.top+1]; return True; }}BOOL Gettop(Stack S,int &ch){//取得栈顶元素，成功返回True，并用ch返回该元素值，失败返回False if(S.top<=-1) return False; else {ch=S.elem[S.top];//显示栈顶元素 return True; }}BOOL StackEmpty(Stack S){//判断堆栈是否已空，若空返回True,不空返回False if(S.top<=-1) return True; else return False;}
[解决办法]
关注...
[解决办法]
关注ing~