求如下有向图的关键路径以及任意两点之间的最短距离?

用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=0i<g->vexnumi++){

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("顶点个数:\n")//顶点数

g->vexnum=n

printf("%d\n",g->vexnum)

printf("边个数:\n")//边数

g->此敏高edgnum=e

printf("%d\n",g->edgnum)

//初始化顶点

for(int j=0j<g->vexnumj++){

g->vexs[j]=a[j]

}

for(int i=0i<g->edgnumi++){

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!\n")

free(g)

continue

}

g->matrix[p1][p2]=b[i][2]

}

for(int i=0i<g->vexnumi++){

for(int j=0j<g->vexnumj++){

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=0i<g->vexnumi++){//列数遍历

for( j=0j<g->vexnumj++){//行数遍历

//如果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("\n")

for(i=0i<g->vexnumi++){

printf("V%d\t",i+1)

}

printf("\n")

for(i=0i<g->vexnumi++){

printf("%d\t",a[i])

}

printf("\n")

printf("最后一个顶点到每个顶点的最长路径:")

for( i=g->vexnum-1i>=0i--){ //列数遍历

for( j=g->vexnum-1j>=0j--){ //行数遍历

//如果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("\n")

for(i=0i<g->vexnumi++){

printf("V%d\t",i+1)

}

printf("\n")

for(i=0i<g->vexnumi++){

printf("%d\t",b[i])

}

printf("\n")

printf("关键路径:\n")

for(i=0i<g->vexnumi++){

if(a[i]==a[g->vexnum-1]-b[i]){

printf("V%c\t",g->vexs[i])

}

}

printf("\n")

}

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\n", s1,  s2, distance[end])

inverse_path[i] = end

pre = path[end]

if(pre == -1){

printf("没有通路!\n")

}else{

while(pre != start){

inverse_path[++i] = pre

pre = path[pre]

}

inverse_path[++i] = start

printf("从%s顶点到%s顶点的最短路径:\n", s1, s2)

for(i >0i--){

sprintf(s1, "V%d", (inverse_path[i]+1))

printf("%s ->", s1)

}

sprintf(s1, "V%d", (inverse_path[i]+1))

printf("%s\n", 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 = 0i <g->vexnumi++){

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 = 0i <g->vexnumi++){

min_dis = INF

for(j = 0j <g->vexnumj++){

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 = 0j <g->vexnumj++){

  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("邻接矩阵:\n")

for (i = 0i <gp->vexnumi++){

for (j = 0j <gp->vexnumj++)

printf("%d  ", gp->matrix[j][i])

printf("\n")

}

CPM_road(gp)

printf("\n")

for(i=0i<gp->vexnumi++){

for(j=0j<gp->vexnumj++){

if(i!=j)

  shortest_path(gp,i, j)

}

}

return 0

}

运行结果

/*

AOE网研究的问题

（1） 完成整个工程至少需要多少时间；

（2） 哪些活动是影响工程的升轿孝关键。

注意：该程序可以计算多条关键路径的情况，

只是输出有些帆岁不仅人意

数据文件aaa.txt的内容

A B 1

A F 3

A H 4

B C 2

F C 6

H I 4

C D 3

C G 4

I G 1

D E 5

G E 3

*/

#include<iostream>

#include<fstream>

using namespace std

#define N 9

#define MAX 10000

int g[N][N]/*存储图,有向图,有权*/

int into[N]/*存储入度*/

int ans[N]/*存储结果序列，模拟栈*/

int ve[N]/*点的最早时间 ve[j]=Max(ve[k]+g[k][j]) */

int vl[N]/*点的最迟时间 vl[i]=Min(v[k]-g[i][k]) */

//int ee[N*N]/*边的最早时间 ee[m]=ve[i]*/

//int el[N*N]/*边的最迟时间 el[m]=vl[j]-g[i][j]*/

bool topoSort()

{

/*初始化*/

for(int i=0i<Ni++)

{

into[i]=-1

ans[i]=-1

ve[i]=0/*初始化ve*/

}

/*计算入度*/

for(int i=0i<Ni++)

{

for(int j=0j<Nj++)

{

if(g[i][j]<MAX) into[j]++

}

}

/*零入度顶点入栈*/

int top=0/*栈顶指针*/

for(int i=0i<Ni++)

{

int j=0

while(0!=into[j])

{

j++

if(j>N)

{

cout<<"晕！有环"<<endl

return false

}

}

/*进入队列*/

ans[i]=j

into[j]=-1

/*计算Ve*/

for(int k=0k<=ik++)

{

if(g[ans[k]][j] <MAX)/*寻找前驱,k是ans中的标号*/

{

cout<<"ans["<<(char(k+'A'))<<"]= "<<ans[k]<<" "

if(ve[j] <ve[ans[k]]+g[ans[k]][j])/*更新数据 ve[j]=Max(ve[k]+g[k][j])*/

{

ve[j] = ve[ans[k]]+g[ans[k]][j]

cout<<"ve["<<(char(j+'A'))<<"]= "<<ve[j]<<endl

}

}

}

cout<<endl<<endl

for(int k=0k<Nk++)

{

if(MAX >g[j][k])

into[k]--

}

}

for(int m=0m<Nm++)

{

cout<<char(ans[m]+'A')<<" "

}

cout<<endl

for(int m=0m<Nm++)

{

cout<<ve[m]<<" "

}

cout<<endl

/*计算vl, vl[i]=Min(v[k]-g[i][k])*/

/*初始化vl*/

int temp=ve[ans[N-1]]

for(int m=0m<Nm++)

{

vl[m]=temp

}

/*计算*/

for(int i=N-1i>=0i--)

{

for(int k=ik<Nk++)

{

if(g[ans[i]][ans[k]] <MAX)/*是后继，k和i都是ans中的标号*/

{

if(vl[ans[i]] >vl[ans[k]]-g[ans[i]][ans[k]])/*更新数据*/

{

vl[ans[i]] = vl[ans[k]]-g[ans[i]][ans[k]]

}

}

}

}

for(int m=0m<Nm++)

{

cout<<vl[m]<<" "

}

cout<<endl

/*找关键点，<i,j>ve[i]==vl[j]-g[i][j]*/

for(int i=0i<N++i)

{

for(int j=ij<Nj++)

{

if(g[ans[i]][ans[j]] <MAX &&ans[i]!=ans[j])/*存在一条边<i,j>*/

{

/*剩余时间为零，该边吵稿在关键路径上，其两个顶点为关键点*/

//cout<<vl[ans[i]]<<" "<<g[ans[i]][ans[j]]<<" "<<ve[ans[i]]<<endl

if(vl[ans[j]]-g[ans[i]][ans[j]]==ve[ans[i]])

{

cout<<"<"<<char(ans[i]+'A')<<" , "<<char(ans[j]+'A')<<"> "

}

}

}

}

cout<<endl

return true

}

int main()

{

/*输入数据*/

fstream fin("aaa.txt")

if(!fin)

{

cerr<<"Cannot open aaa.txt"<<endl

}

/*初始化邻接表*/

for(int m=0m<Nm++)

{

for(int n=0n<Nn++)

{

if(m==n) g[m][n]=0

else g[m][n]=MAX

}

}

//memset(g, MAX, sizeof(g))

char i,j

int k

while(fin>>i>>j>>k)

{

g[(int)(i-'A')][(int)(j-'A')]=k

}

for(int m=0m<Nm++)

{

for(int n=0n<Nn++)

cout<<g[m][n]<<" "

cout<<endl

}

/*拓扑排序*/

int noRing=topoSort()

if(!noRing)

{

return 0

}

return 1

}

---