最长路径算法代码实现c语言

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

用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;

}

运行结果

2. 如何用迪杰斯特拉算法 在C语言上写一个 查找最长路径的程序

可以参考李春葆的数据结构，上面有类似的！

3. c语言运用邻接矩阵求最短路径中的最长路径问题

同问、

4. 编写c++算法求任意二叉树中一条最长的路径，并输出此路径上各结点的值

#include <stdio.h>
#define MaxSize 1000

typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild;
}BiTNode,*BiTree;

void LongestPath(BiTree bt)//求二叉树中的第一条最长路径长度,并输出最长路径上的节点
{
BiTree p = bt, l[MaxSize], s[MaxSize]; //l, s是栈，元素是二叉树结点指针，l中保留当前最长路径中的结点
int i,top = 0, tag[MaxSize], longest = 0;
while (p || top >0)
{
while (p)
{
s[++top] = p;
tag[top] = 0;
p = p->lchild;
} //沿左分枝向下
if (tag[top] == 1) //当前结点的右分枝已遍历
{
if (!s[top]->lchild && !s[top]->rchild) //只有到叶子结点时，才查看路径长度
if (top>longest)
{
for (i = 1; i <= top; i++)
l[i] = s[i];
longest = top;
top--;
}//保留当前最长路径到l栈，记住最高栈顶指针，退栈
}
else if (top>0)
{
tag[top] = 1;
p = s[top]->rchild;
} //沿右子分枝向下
}//while(p!=null||top>0)
int k = 0;
for (k = 0; k < longest; k++)
{
printf("%d ", l[k]->data);
}
}//结束LongestPath

5. c语言编写路线

#include <stdio.h>
#include <malloc.h>
#include<stdlib.h>
#define MAX 100
#define MAXNUM 10000000
int previous[MAX-1];// 求路径需要
int pp[MAX-1];// 记录最短路径
typedef struct graphnode
{
int vexnum; //顶点
int arcnum; //弧
int gra[MAX][MAX]; //邻接矩阵表示0或1
}Graph;
int dist[MAX]; // 最短距离
int arc[MAX][MAX]; // 权

int main()
{
void Dijkstra(Graph *g,int v);
int i,j,n,m;
int v; //源点
Graph *G;
G=(Graph *)malloc(sizeof(Graph));
printf("vexnum:\n");
scanf("%d",&G->vexnum);
printf("arcnum:\n");
scanf("%d",&G->arcnum);
printf("graph:\n");
for(i=0;i<G->vexnum;i++)
for(j=0;j<G->vexnum;j++)
{
scanf("%d",&G->gra[i][j]);
}
for(i=0;i<G->vexnum;i++)
for(j=0;j<G->vexnum;j++)
{
if(G->gra[i][j]==1)
{
printf("请输入%d到%d的权值:",i,j);
scanf("%d",&arc[i][j]);//若有弧 则输入i到j直接的权
}
else
arc[i][j]=MAXNUM;
}
printf("请输入源点v的值:");
scanf("%d",&v);
Dijkstra(G,v);
printf("请输入源点所要到达的点：\n");
scanf("%d",&n);
pp[0]=0;
i=1;
m=n;// 记录n的值
while(n!=0)// 求0到其他点路径
{
pp[i]=previous[n];
i++;
n=previous[n];

}
printf("Path:0 -> ");
for(j=G->vexnum-1;j>=0;j--)
if(pp[j]!=0)
printf(" %d -> ",pp[j]);
printf("%d\n",m);
return 0;

}
void Dijkstra(Graph *G,int v)
{
int previous[MAX-1];
int newdist;
bool sign[MAX];
if(v<0||v>MAX-1)
{
printf("该源点不存在！\n");
return;
}

for(int i=0;i<G->vexnum;i++) //初始化
{
dist[i]=arc[v][i];
sign[i]=false;
if(dist[i]==MAXNUM)
previous[i]=0;
else
previous[i]=v;
}

dist[v]=0;
sign[v]=true;

for(i=0;i<G->vexnum;i++) // i<n-1 待定
{
float temp=MAXNUM;
int u=v; //u 中间变量
for(int j=0;j<G->vexnum;j++)
if((!sign[j])&&(dist[j]<temp))
{
u=j;
temp=dist[j];
}
sign[u]=true;
for(j=0;j<G->vexnum;j++)
if((!sign[j])&&(arc[u][j]<MAXNUM))
{
newdist=dist[u]+arc[u][j];
if(newdist<dist[j])
{
dist[j]=newdist;
previous[j]=u;
}

}
}
for(i=0;i<G->vexnum;i++)
if(dist[i]!=MAXNUM)
printf("从%d到%d的最短路径是 %d\n",v,i,dist[i]);
else
printf("从%d到%d无最短路径\n",v,i);
printf("\n");

}
这是Dijkstra算法求单源最短路径算法 上程序中 假定顶点从0开始，搜索整个图，然后求出0到其他各点的最短距离，存放在dist数组中，main函数后面几行是求0到其他各点的路径 基本上能满足你的要求了

6. 求帮算法作业！用动态规划法求解最长路径问题

先对图进行拓扑排序 一个结果为s b a c d t 拓扑排序的时候初始化dist[i] 表示从s到i的距离
dist[i]=max{dist[u]+edge[u][i], dist[i]}.
i从s取到t 最终得结果

7. 用C语言实现以下问题并讲解大概思路和所用算法，非常感谢！

唔，你这个问题的话，因为你这个不指定起点，所以应该是多源最长路径问题，我参考了一下多源最短路径的Floyd算法如下，不知道可不可以啊：
首先是输入
g[i][j]表示从i城市到j城市所需要的路费，

int g[M][M]={{null,2,1,null},{null,null,5,4},{null,null,null,null},{null,null,null,null}}
null表示两个城市之间不存在路径，看上去这个数组很浪费，因为Floyd算法是可以针对更复杂的图进行计算的算法，具体有没有更优算法我也不知道=。=
然后让M=你输入的城市数量-1，这里M=4
输入设置好以后，就可以进行循环比较了，通过三重循环的比较，最终得到D[4][4]这样一个数组，这个数组中的D[i][j]表示从i城市到j城市所需要的最高的路费，然后再通过比较数组D中最大值，应该就可以得出结果了。

这里复制一下原理：
Floyd-Warshall算法的原理是动态规划。
设Di,j,k为从i到j的只以(1..k)集合中的节点为中间节点的最短路径的长度。
若最短路径经过点k，则Di,j,k = Di,k,k − 1 + Dk,j,k − 1；
若最短路径不经过点k，则Di,j,k = Di,j,k − 1。
因此，Di,j,k = min(Di,k,k − 1 + Dk,j,k − 1,Di,j,k − 1)。（而我们是求最长，所以应该换成max就可以了）

void floyd(int g[M][M],int D[M][M])
{
for(int k = 0;k<M;k++)
for(int i = 0;i<M;i++)
{
for(int j = 0;j<M;j++)
{
if(k == 0)//k=0，第一轮循环时，先将基础值赋值给D数组
{
if(g[i][j]!=null)
D[i][j] =g[i][j];
else
{
g[i][j]=-30000;//在k=0的第一轮循环中，让没有路径的地方等于一个大的负数，这样之后的比较就不需要重复的判断非空了
D[i][j]=-30000;
}}

else//当k不等于0时，也就是第二轮循环之后,进行最长路径的比较和计算，大的值赋值给D数组
{
D[i][j] = MAX(D[i][j],D[i][k]+D[k][j]);
}

}
}
}
最后再写个循环，取出数组D中的最大值就可以得到最大路程了然后再算最大路费，如果前面的算法没错的话。
我的感觉的话，Floyd-Warshall算法比较容易实现，不需要特殊的数据结构，就是可能算法的时间和空间复杂度比较高，不知道你怎么看

8. 跪求最短（长）路径算法，（按要求的）Dijkstra算法C/C++源代码

int Locate(MGraph G,VexType v)
{
for(int i=0;i<G.vexnum;++i)
if(strcmp(v,G.vexs[i])==0)
return i;
return -1;
}
void ShortestPath(MGraph G,VexType v,int dist[],int path[])
{//求顶点v到其余各个顶点的最短路径长度，并存放在dist数组中，path数组存放路径
int S[MAX_VEX_NUM]={0};
int i,j,k;
for(i=0;i<G.vexnum;++i)
{
k=Locate(G,v);
dist[i]=G.arcs[k][i];//初始化数组dist
if(k!=i&&dist[i]<INFINITY)path[i]=k;
else path[i]=-1;//初始化数组path
}
S[k]=1;dist[k]=0;
for(i=1;i<G.vexnum;++i)//循环n-1次
{
int min=INFINITY;
int u=k;
for(j=0;j<G.vexnum;++j)
if(!S[j]&&dist[j]<min)
{u=j;min=dist[j];}
S[u]=1;
for(j=0;j<G.vexnum;++j)
if(!S[j]&&G.arcs[u][j]<INFINITY&&dist[u]+G.arcs[u][j]<dist[j])
{
dist[j]=dist[u]+G.arcs[u][j];
path[j]=u;
}
}
}
void Print(MGraph G,int dist[],int path[])
{
for(int i=1;i<G.vexnum;++i)
{
if(path[i]==-1)cout<<"v0到"<<G.vexs[i]<<"没有路径\n";
else
{
int stack[MAX_VEX_NUM],top=0,k;
stack[top++]=i;k=path[i];
while(k>=0)
{stack[top++]=k;k=path[k];}
while(--top>=0)
cout<<G.vexs[stack[top]]<<"->";
cout<<"最短路径长度="<<dist[i]<<endl;
}
}
}

9. 请高手帮忙修改，编写一个求有向无环图中最长路径的数据结构C语言版程序的题

把代码重新贴一下吧，