最長路徑演算法代碼實現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語言版程序的題

把代碼重新貼一下吧，