c語言求任意兩點之間最短路徑_c語言最短路徑問題

⑴ 求c語言最短路徑演算法

#include <iostream>
using namespace std;

const int maxnum = 100;
const int maxint = 999999;

// 各數組都從下標1開始
int dist[maxnum]; // 表示當前點到源點的最短路徑長度
int prev[maxnum]; // 記錄當前點的前一個結點
int c[maxnum][maxnum]; // 記錄圖的兩點間路徑長度
int n, line; // 圖的結點數和路徑數

// n -- n nodes
// v -- the source node
// dist[] -- the distance from the ith node to the source node
// prev[] -- the previous node of the ith node
// c[][] -- every two nodes' distance
void Dijkstra(int n, int v, int *dist, int *prev, int c[maxnum][maxnum])
{
bool s[maxnum]; // 判斷是否已存入該點到S集合中
for(int i=1; i<=n; ++i)
{
dist[i] = c[v][i];
s[i] = 0; // 初始都未用過該點
if(dist[i] == maxint)
prev[i] = 0;
else
prev[i] = v;
}
dist[v] = 0;
s[v] = 1;

// 依次將未放入S集合的結點中，取dist[]最小值的結點，放入結合S中
// 一旦S包含了所有V中頂點，dist就記錄了從源點到所有其他頂點之間的最短路徑長度
// 注意是從第二個節點開始，第一個為源點
for(int i=2; i<=n; ++i)
{
int tmp = maxint;
int u = v;
// 找出當前未使用的點j的dist[j]最小值
for(int j=1; j<=n; ++j)
if((!s[j]) && dist[j]<tmp)
{
u = j; // u保存當前鄰接點中距離最小的點的號碼
tmp = dist[j];
}
s[u] = 1; // 表示u點已存入S集合中

// 更新dist
for(int j=1; j<=n; ++j)
if((!s[j]) && c[u][j]<maxint)
{
int newdist = dist[u] + c[u][j];
if(newdist < dist[j])
{
dist[j] = newdist;
prev[j] = u;
}
}
}
}

// 查找從源點v到終點u的路徑，並輸出
void searchPath(int *prev,int v, int u)
{
int que[maxnum];
int tot = 1;
que[tot] = u;
tot++;
int tmp = prev[u];
while(tmp != v)
{
que[tot] = tmp;
tot++;
tmp = prev[tmp];
}
que[tot] = v;
for(int i=tot; i>=1; --i)
if(i != 1)
cout << que[i] << " -> ";
else
cout << que[i] << endl;
}

int main()
{
freopen("input.txt", "r", stdin);
// 各數組都從下標1開始

// 輸入結點數
cin >> n;
// 輸入路徑數
cin >> line;
int p, q, len; // 輸入p, q兩點及其路徑長度

// 初始化c[][]為maxint
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
c[i][j] = maxint;

for(int i=1; i<=line; ++i)
{
cin >> p >> q >> len;
if(len < c[p][q]) // 有重邊
{
c[p][q] = len; // p指向q
c[q][p] = len; // q指向p，這樣表示無向圖
}
}

for(int i=1; i<=n; ++i)
dist[i] = maxint;
for(int i=1; i<=n; ++i)
{
for(int j=1; j<=n; ++j)
printf("%8d", c[i][j]);
printf("
");
}

Dijkstra(n, 1, dist, prev, c);

// 最短路徑長度
cout << "源點到最後一個頂點的最短路徑長度: " << dist[n] << endl;

// 路徑
cout << "源點到最後一個頂點的路徑為: ";
searchPath(prev, 1, n);
}

⑵ 怎樣作用c語言實現一個城市的公招線路圖，及求任意兩個站點間的最短路徑和換乘方法。

這是我寫的程序和運行的結果，如果有不會的地方依然可以問我。
/*
首先我想說明幾點問題。
1.我不知道你的題意中的路徑是單向的還是雙向的，不過我把路徑設置成雙向的了
2.說一下我程序的輸入，首先輸入一個n，表示該圖中有n條路；然後有n行，每行
兩個數x, y（1<=x, y<=99），表示這兩個地點有一條路徑。最後輸入兩個數，
表示計算這兩點之間所有的路徑
3.我的思路用的是深搜，不過廣搜也是可以的
*/
#include <stdio.h>
#include <math.h>
int path[100][100];///path[i][j]為0表示i, j兩點之間不通，為1表示有一條路
int stack[120], m=1, n, x, y;///存儲路徑
void dfs(int p)
{
int i, j;
for(i=1; i<=100; i++)
{
if(path[p][i]==1)
{
if(i == y)///如果深搜到了終點，就輸出剛才經過的路徑
{
for(j=0; j<m; j++)
{
printf("%-5d", stack[j]);
}
printf("%-5d\n", y);
}
else///如果該點不是終點
{
stack[m] = i;///將該點存起來
m++;
dfs(i);///接著深搜
m--;
}
}
}
}
int main()
{
int i, j;
memset(path, 0, sizeof(path));
scanf("%d", &n);
for(i=0; i<n; i++)
{
scanf("%d %d", &x, &y);
path[x][y] = path[x][y] = 1;///這兩點之間有路徑
}
scanf("%d %d", &x, &y);
stack[0] = x;
dfs(x);
}

⑶ C語言最短路徑演算法問題，Floyd演算法行不通

要用演算法你也要先理解了再用啊，不懂你是修改了什麼，反正floyd肯定不是你這么寫，floyd要把中間結點的遍歷放在最三重循環的最外層。另外，求最短路徑是怎麼走的完全可以在更新最短路徑長度的過程中記錄中間結點是什麼，這並非演算法不能解決，而在於使用演算法的人是否真正懂得演算法過程，以及待解決的問題是否需要求解這方面的問題。

⑷ C語言求兩點之間的最短路徑

#include<graphics.h>
#include<stdio.h>
# define n 6
# define NULL 0
#define UP 72
#define DOWN 80
#define ESC 27
#define Enter 13
int i1=0,j1=3,m1=0,n1=0;
int start=0;
char str2[][100]={"THE INTRODUTION OF THE ROUTINE !",
"AUGMENT THE RELATIVE DATA !",
"SEARCH FOR THE INFORMATION !",
"QUIT THE ROUTINE !"};
char str3[][100]={"THE ROUTINE WAS PROGRAMED IN ",
" 2006--07--10",
"PROGRAMER : ",
"CAO JUN BIN "};

int dd[n+1][n+1], pp[n+1][n+1],a[n];
typedef struct
{int number; int edge[n+1][n+1]; }graph;
graph g;
int maxdist=2000,mindist;
struct viewpoint
{int x; int y; int number; char inf[10]; }bd[n];

struct point
{int number; int x_1; int y_1; }point[n];
typedef struct point f;
struct path
{int V1; int V2; int length; }p[n*n/2];

void mainmenu ();
void con();
void choosepoint() ;
void interface();
void interface1();
void again();
void drawbuilding();
void drawedge();
void floyd(graph g,int m, int dd[n+1][n+1],int pp[n+1][n+1]);
void display(int i,int j,int pp[n+1][n+1],int dd[n+1][n+1]);
void drawpath();
void buildingmap( );
void pathmap( );
main()
{ int gdriver=9,gmode=2;
initgraph(&gdriver,&gmode,"c:\\TURBOC2");
mainmenu();
}

void mainmenu ()
{int a,flag=1,i,j; char c; char str[10]; setbkcolor(BLACK); setcolor(LIGHTGRAY); rectangle(20,20,600,475); settextstyle(4,0,4); setcolor(LIGHTRED); outtextxy(160,70,"THE MAIN MENU "); settextstyle(3,0,1); setcolor(CYAN); outtextxy(160,160,str2[0]); outtextxy(160,200,str2[1]); outtextxy(160,240,str2[2]); outtextxy(160,280,str2[3]); while(flag){ c=getch(); switch(c){case DOWN:i1++;j1++; m1=i1%4;n1=j1%4; con();break; case UP :if(i1==-1)i1=3;if(j1==-1)j1=3; m1=i1%4;n1=j1%4;a=m1;m1=n1;n1=a; con(); i1--;j1--;break; case ESC :flag=0;break; case Enter:cleardevice(); if(m1==0){interface1();getch();cleardevice(); mainmenu(); }

if(m1==1){ setbkcolor(BLACK);
setcolor(YELLOW);
rectangle(20,20,600,475);
rectangle(30,30,590,465) ;
setcolor(LIGHTRED);
settextstyle(3,0,1);
setcolor(LIGHTRED);
outtextxy(160,160,"PLESE CHOOSE THE SEVICE !");
outtextxy(120,200," AUGMENT THE INFORMATION OF THE BUILDING (B)!");
outtextxy(120,240," AUGMENT THE INFORMATION OF THE BUILDING (P) !");
switch(getch()){case'B':{cleardevice();buildingmap();cleardevice();};break;
case 'P':{cleardevice();pathmap();cleardevice();};break;
default: cleardevice();mainmenu();}
}
if(m1==2){
interface();
getch();}
if(m1==3){exit(0); }
}

}

}
void con()
{setcolor(YELLOW); outtextxy(160,160+m1*40,str2[m1]); setcolor(CYAN); outtextxy(160,160+n1*40,str2[n1]); }
void interface()
{ int i,j;
char str[10];
setbkcolor(BLACK);
setcolor(LIGHTGRAY);
rectangle(20,20,600,100);
rectangle (20,20,600,470);
rectangle (20,100,450,470) ;
rectangle(20,350,450,470);
rectangle(20,100,300,350);
settextstyle(3,0,3);
outtextxy(200,30,"WELCOME TO");
outtextxy(120,60,"NORTHEAST DIANLI UNIVERSITY!") ;
outtextxy(460,200,"FROM : ___");
outtextxy(485,250,"TO : ___");
settextstyle(2,0,5);
rectangle(475,315,535,335);
rectangle(475,365,535,385);
outtextxy(455,150,"(PLEASE INPUT!)");
outtextxy(175,360,"THE RESULT !");
outtextxy(500,320,"F");
outtextxy(500,370,"Q");
outtextxy(480,400,"Input");
outtextxy(460,420, "the number 1-->6");
setcolor(RED);
drawbuilding();
drawedge();
i=0;
while(i<'1'||i>'6') i=getch();
sprintf(str,"%c",i);
outtextxy(560,205,str);
while(j<'1'||j>'6') j=getch();
sprintf(str,"%c",j);
outtextxy(560,255,str);
i=i-48;j=j-48;
floyd(g,n,dd[n+1][n+1],pp[n+1][n+1]);
display (i,j,pp[n+1][n+1], dd[n+1][n+1]);
drawpath( );
}
void interface1()
{
setbkcolor(BLACK);
setcolor(YELLOW);
rectangle(20,20,600,475);
rectangle(30,30,590,465) ;
settextstyle(4,0,4);
setcolor(LIGHTRED);

settextstyle(3,0,1);
setcolor(LIGHTRED);
outtextxy(160,160,str3[0]);
outtextxy(160,200,str3[1]);
outtextxy(210,240,str3[2]);
outtextxy(210,280,str3[3]);

}

void again()
{int i; if(start==0) {for (i=0;i<300;i++) delay(1000);}
}

void drawbuilding()
{ int i,a;char str[10];
FILE *fp;
if ((fp=fopen("map.dat","r"))==NULL)
{
printf("Can not open the file of map.dat.\n");
exit(0);
}

for(i=0;i<n;i++)
{fread(&bd[i],sizeof(struct viewpoint),1,fp); point[i].number=bd[i].number; point[i].x_1=bd[i].x; point[i].y_1=bd[i].y; setcolor(RED); a=bd[i].number; sprintf(str,"%d",a); again(); circle(bd[i].x,bd[i].y,8); setcolor(LIGHTGRAY); outtextxy(bd[i].x-2,bd[i].y-5,str); outtextxy(310,i*30+120,str); outtextxy(325,i*30+120,":"); outtextxy(340,i*30+120,bd[i].inf); again(); }

fclose(fp);

}

void drawedge()
{ FILE *fp;char str[10];
int i,j,x1,x2,y1,y2,a;
if((fp=fopen("pmap.dat","r"))==NULL)
{ printf ("can't open the file\n");
exit(0);
}

for (i=0;i<=n;i++)
{for (j=0;j<=n;j++) g.edge[i][j]=maxdist;}
for(j=1;j<=n;j++)
g.edge[j][j]=0;
while(!feof(fp))
{ fread(&p[i],sizeof(struct path),1,fp);
if(p[i].V1!=0)
{
{g.edge[p[i].V1][p[i].V2]=p[i].length; g.edge[p[i].V2][p[i].V1]=p[i].length; }
setcolor(LIGHTBLUE);
for(j=0;j<n;j++)
{if(p[i].V1-point[j].number==0) {x1=point[j].x_1; y1=point[j].y_1; }
}

for(j=0;j<n;j++)
{if(p[i].V2==point[j].number) { x2=point[j].x_1; y2=point[j].y_1; }

}
line(x1,y1,x2,y2);
setcolor(LIGHTGRAY);
a=p[i].length;
sprintf(str,"%d",a);
outtextxy((x1+x2)/2,(y1+y2)/2,str);
again();
}
}

fclose(fp);
start=1;
}

void floyd(graph g,int m,int dd[n+1][n+1],int pp[n+1][n+1])
{int i,j,k,w; for(i=0;i<=m;i++) {for(j=0;j<=m;j++) dd[i][j]=maxdist;}

for(i=0;i<=m;i++)
{for(j=0;j<=m;j++) pp[i][j]=0; }
for(i=1;i<=m;i++)
{ for(j=1;j<=m;j++)
{dd[i][j]=g.edge[i][j]; if(dd[i][j]<maxdist&dd[i][j]!=0) pp[i][j]=j; else pp[i][j]=-1; } }
for(k=1;k<=m;k++)
for(i=1;i<=m;i++)
for(j=1;j<=m;j++)
if(dd[i][j]>(dd[i][k]+dd[k][j]))
{
dd[i][j]=dd[i][k]+dd[k][j];
pp[i][j]=k;
pp[j][i]=k;
}
}
void display(int i,int j,int pp[n+1][n+1],int dd[n+1][n+1])
{
int pre,flag,k,w=40;int m=0;
int str[10];
pre=k=j;
do { pre=pp[i][pre];
if(pre!=k)
sprintf(str,"%d",k);
outtextxy(120+w,390,str);

outtextxy(130+w,390,"<--");
a[m]=k;
m=m+1;
w=w+40;
k=pre;
pre=pp[i][pre];
flag=pre;
}while(flag!=k) ;

sprintf(str,"%d",flag);
outtextxy(120+w,390,str);
a[m]=flag;
outtextxy(130+w,390,"<--");
sprintf(str,"%d",i);
outtextxy(160+w,390,str);
a[m+1]=i;
a[m+2]=NULL;

outtextxy(60,390,"THE WAY IS:");
outtextxy(60,420,"THE SHORTEST WAY IS :");
sprintf(str,"%d",dd[i][j]);
outtextxy(240,420,str);

}
void drawpath( )
{ int i,j,x1,x2,y1,y2;
char l;
setcolor(RED);
for(i=0;i<n;i++)
{if(a[i+1]!=NULL) { again(); for(j=0;j<n;j++) {if(a[i]-point[j].number==0) {x1=point[j].x_1; y1=point[j].y_1; }
}

for(j=0;j<n;j++)
{if(a[i+1]==point[j].number) { x2=point[j].x_1; y2=point[j].y_1; }

}
line(x1,y1,x2,y2);

}
}
i=0;
while(i!='Q'&i!='F'&i!='q'&i!='f') i=getch();
switch(i)
{ case 'Q': {cleardevice(); mainmenu();};break;
case 'q': {cleardevice(); mainmenu();};break;
case 'F': {cleardevice();interface();};break;
case 'f': {cleardevice();interface();};break;
}
}

void buildingmap( )
{ FILE *fp;
int i;
setbkcolor(BLACK);
setcolor(YELLOW);
rectangle(100,40,450,475);
rectangle(110,50,440,465) ;

setcolor(LIGHTRED);
settextstyle(2,0,4);
setcolor(LIGHTRED); if((fp=fopen("ss1-map","ab"))==NULL)
{ printf ("can't open the file\n");
exit(0);
}
outtextxy(160,100,"Please input the information of the building! ");
for(i=0;i<n;i++)
{ outtextxy(160,100+20*(i+1),"<--input data:" );
scanf("%d,%d,%d,%s\n",&bd[i].x,&bd[i].y,&bd[i].number,bd[i].inf );
if(fwrite(&bd[i],sizeof(struct viewpoint),1,fp)!=1)
printf("file write error\n");
}
fclose(fp);
if(getch()=='Q') {cleardevice();mainmenu();}
}
void pathmap()
{FILE *fp; int i; cleardevice(); setbkcolor(BLACK); rectangle(100,40,450,475); rectangle(110,50,440,465) ; setcolor(LIGHTRED); settextstyle(2,0,4); if((fp=fopen("pp1-map","ab"))==NULL) { printf ("can't open the file\n"); exit(0); }
fseek(fp,0L,2);
outtextxy(160,100,"Please input the information of the building! ");
for(i=0;i<(n*n/2);i++)
{ outtextxy(160,100+20*(i+1),"<--input data:" );
scanf("%d,%d,%d\n",&p[i].V1,&p[i].V2,&p[i].length );
if(fwrite(&p[i],sizeof(struct path),1,fp)!=1)
printf("file write error\n");
}
fclose(fp);
if(getch()=='Q') {cleardevice();mainmenu();}
}

⑸ c語言編寫請簡單點。用帶權鄰接矩陣輸入一幅無向圖，使用兩種不同的演算法計算出最短路徑長度並輸出路徑。

//Floyed 實現賦權無向圖定點對間的最短路徑，時間復雜度O(n^3)
1，從任意一條單邊路徑開始。所有兩點之間的距離是邊的權，或者無窮大，如果兩點之間沒有邊相連。
2，對於每一對頂點 u 和 v，看看是否存在一個頂點 w 使得從 u 到 w 再到 v 比己知的路徑更短。如果是更新它。
#include<stdio.h>
int main()
{
int c[20][20],parth[20][20],i,j,k,t1,t2,t3,n,x,y,re;
printf("輸入圖的頂點數:");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
printf("輸入邊(%d,%d)的權值,若不存在輸入10000:",i,j);
scanf("%d",&c[i][j]);
}
}
如果是有向圖就刪掉這里"//for(i=1;i<=n;i++)
//{
///////////////////////////////////////for(j=1;j<=i;j++)
////////////////////////////////////////c[i][j]=c[j][i];
/////////////////////////////////////////}"
for(i=1;i<=n;i++)
c[i][i]=0;//自己到自己的權值為0
for(i=1;i<=n;i++) //初始化路徑
{
for(j=1;j<=n;j++)
parth[i][j]=0;
}
for(k=1;k<=n;k++)//k是中間節點，i是起點j是中點。其實就是枚舉中間節點，來求i j 的最短路徑
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
t1=c[i][k];
t2=c[k][j];
t3=c[i][j];
if(t1!=10000&&t2!=10000&&(t3==10000||t1+t2<t3)) //鬆弛覆蓋原來的最短路
{c[i][j]=t1+t2,parth[i][j]=k;}//記錄i j的中間點是k
}
}
}
while(1)//也可以用遞歸的形式輸出parth
{
printf("輸入2點:");
scanf("%d%d",&x,&y);
printf("最短距離為%d\n",c[x][y]);
printf("%d ",x);
re=y;
while(parth[x][y]!=0)
{
printf("%d ",parth[x][y]);
y=parth[x][y];
}
printf("%d\n",re);
}
return 0;
}

⑹ C語言最短路徑

int main()
{
int G[100][100] = {};
//一個記錄圖的鄰接矩陣
int a, b, w;
//輸入一共有7條邊, 5個點
int i, j, k;
for(i = 1;i <= 5;i++)
for(j = 1;j <= 5;j++)
G[i][j] = 9999999;
for(i = 1;i <= 7;i++)
{
scanf("%d %d %d", &a, &b, &w);//輸入每條邊的信息，a和b代表這條邊的兩個頂點w代表兩個點的距離
G[a][b] = w;
G[b][a] = w;
}
for(k = 1;k <= 5;k++)
for(i = 1;i <= 5;i++)
for(j = 1;j <= 5;j++)
if(G[i][j] > G[i][k] + G[k][j])
G[i][j] = G[i][k] + G[k][j];
printf("%d", G[1][4]);//輸出兩點之間的最短路，這里的兩個點是3和5
return 0;
}
G[i][j]代表i到j的距離，甲，乙，丙，丁，戊用1，2，3，4，5代替
如果你還不懂的話，就看一些關於圖論的問題，這個最短路是圖論中的一個經典題

⑺ 最短路徑演算法 C語言

#include<stdio.h>

#defineMAXNODE108

intpath[MAXNODE+1][MAXNODE+1]={0};

intmain(void)
{
FILE*fpr,*fpw;
intva,vb,i,j,k;

fpr=fopen("in.txt","r");/*讀取的文件名稱in.txt*/
fpw=fopen("out.txt","w");/*path的數據在out.txt中展現*/

while(fscanf(fpr,"%d%d",&va,&vb)!=EOF)
path[va][vb]=path[vb][va]=1;

for(k=1;k<=MAXNODE;++k){
for(i=1;i<=MAXNODE;++i){
for(j=1;j<=MAXNODE;++j){
if(!path[i][k]||!path[k][j])
continue;

if(!path[i][j])
path[i][j]=path[i][k]+path[k][j];
elseif(path[i][j]>path[i][k]+path[k][j])
path[i][j]=path[i][k]+path[k][j];
}
}
}

for(i=1;i<=MAXNODE;++i){
for(j=1;j<=MAXNODE;++j){
if(i==j)
fprintf(fpw,"%-10d",0);
elseif(path[i][j])
fprintf(fpw,"%-10d",path[i][j]);
else
fprintf(fpw,"%-10d",-1);
}
fprintf(fpw,"
");
}

return0;
}

注意：floyd演算法中k為最外層，這是動態規劃的思想，不能改變i,j,k的順序！！！

這是之前的答案的錯誤之處。

-1表示不通。

具體程序分析，我可以加你QQ，願意的話，你把QQ寫給我。

⑻ c語言最短路徑問題。

這是圖中任意二點的最短距離演算法吧。 Floyd演算法。

這程序太亂了。

num這個參數也不知道什麼意思，反正就是Floyd演算法。這個演算法就是一個三層循環，數據結構的課本有說過，還有一些處理，就是最短距離的走法，課本都有說，網上也有，去參考下吧。

⑼ 求c++ 程序網路上兩點間的最短路徑

/*
* File: shortest.c
* Description: 網路中兩點最短路徑 Dijkstra 演算法
* Shortest Path Dijkstra Algorithm
* Created: 2001/11/25
* Author: Justin Hou [mailto:[email protected]]
*/

#include <stdio.h>
#define true 1
#define false 0
#define I 9999 /* 無窮大 */
#define N 20 /* 城市頂點的數目 */

int cost[N][N] = {
{0,3,I,I,I,1,I,I,I,I,I,I,I,I,I,I,I,I,I,I},
{3,0,5,I,I,I,6,I,I,I,I,I,I,I,I,I,I,I,I,I},
{I,5,0,4,I,I,I,1,I,I,I,I,I,I,I,I,I,I,I,I},
{I,I,4,0,2,I,I,I,6,I,I,I,I,I,I,I,I,I,I,I},
{I,I,I,2,0,I,I,I,I,7,I,I,I,I,I,I,I,I,I,I},
{1,I,I,I,I,0,1,I,I,I,2,I,I,I,I,I,I,I,I,I},
{I,6,I,I,I,1,0,6,I,I,I,7,I,I,I,I,I,I,I,I},
{I,I,1,I,I,I,6,0,2,I,I,I,3,I,I,I,I,I,I,I},
{I,I,I,6,I,I,I,2,0,8,I,I,I,4,I,I,I,I,I,I},
{I,I,I,I,7,I,I,I,8,0,I,I,I,I,5,I,I,I,I,I},
{I,I,I,I,I,2,I,I,I,I,0,4,I,I,I,3,I,I,I,I},
{I,I,I,I,I,I,7,I,I,I,4,0,3,I,I,I,4,I,I,I},
{I,I,I,I,I,I,I,3,I,I,I,3,0,3,I,I,I,5,I,I},
{I,I,I,I,I,I,I,I,4,I,I,I,3,0,7,I,I,I,2,I},
{I,I,I,I,I,I,I,I,I,5,I,I,I,7,0,I,I,I,I,3},
{I,I,I,I,I,I,I,I,I,I,3,I,I,I,I,0,5,I,I,I},
{I,I,I,I,I,I,I,I,I,I,I,4,I,I,I,5,0,8,I,I},
{I,I,I,I,I,I,I,I,I,I,I,I,5,I,I,I,8,0,6,I},
{I,I,I,I,I,I,I,I,I,I,I,I,I,2,I,I,I,6,0,4},
{I,I,I,I,I,I,I,I,I,I,I,I,I,I,3,I,I,I,4,0}
};
int dist[N]; /* 存儲當前最短路徑長度 */
int v0 = 'A' - 65; /* 初始點是 A */

void main()
{
int final[N], i, v, w, min;

/* 初始化最短路徑長度數據，所有數據都不是最終數據 */
for (v = 0; v < N; v++) {
final[v] = false;
dist[v] = cost[v0][v];
}

/* 首先選v0到v0的距離一定最短，最終數據 */
final[v0] = true;

/* 尋找另外 N-1 個結點 */
for (i = 0; i < N-1; i++) {
min = I; /* 初始最短長度無窮大 */

/* 尋找最短的邊 */
for (w = 0; w < N; w++) {
if (!final[w] && dist[w] < min) {
min = dist[w];
v = w;
}
}
final[v] = true; /* 加入新邊 */

for (w = 0; w < N; w++) { /* 更新 dist[] 數據 */
if (!final[w] && dist[v] + cost[v][w] < dist[w]) {
dist[w] = dist[v] + cost[v][w];
}
}
}

for (i = 0; i < N; i++) { /* 顯示到監視器 */
printf("%c->%c: %2d\t", v0 + 65, i + 65, dist[i]);
}
});
if (left == NULL || right == NULL) {
fprintf(stderr,"Error malloc.\n");
exit(-1);
}
/* 初始化左右分枝結點 */
left->bound = root.bound; /* 繼承父結點的下界 */
left->matrix = LeftNode(root.matrix, selectedEdge); /* 刪掉分枝邊 */
left->path = root.path; /* 繼承父結點的路徑，沒有增加新邊 */
left->left = NULL;
left->right = NULL;

right->bound = root.bound;
right->matrix = RightNode(root.matrix, selectedEdge, root.path);/* 刪除行列和迴路邊 */
right->path = AddEdge(selectedEdge, root.path); /* 加入所選邊 */
right->left = NULL;
right->right = NULL;

/* 歸約左右分枝結點 */
left->bound += Simplify(&left->matrix);
right->bound += Simplify(&right->matrix);

/* 鏈接到根 */
root.left = left;
root.right = right;

/* 顯示到監視器 */
puts("Right Branch:\n------------");
ShowMatrix(right->matrix);
puts("Left Branch:\n-----------");
ShowMatrix(left->matrix);

/* 如果右結點下界小於當前最佳答案，繼續分枝搜索 */
if (right->bound < minDist) {
BABA(*right);
}
/* 否則不搜索，因為這條枝已經不可能產生更佳路線 */
else {
printf("Current minDist is %d, ", minDist);
printf("Right Branch's Bound(= %d).\n", right->bound);
printf("This branch is dead.\n");
}

/* 如果右結點下界小於當前最佳答案，繼續分枝搜索 */
if (left->bound < minDist) {
BABA(*left);
}
/* 否則不搜索，因為這條枝已經不可能產生更佳路線 */
else {
printf("Current minDist is %d, ", minDist);
printf("Left Branch's Bound(= %d).\n", left->bound);
printf("This branch is dead.\n");
}

printf("The best answer now is %d\n", minDist);
return (minPath);
}

/* 修補路徑 */
PATH MendPath(PATH path, MATRIX c)
{
int row, col;
EDGE edge;
int n = c.citiesNumber;

for (row = 0; row < n; row++) {
edge.head = row;
for (col = 0; col < n; col++) {
edge.tail = col;
if (c.distance[row][col] == 0) {
path = AddEdge(edge, path);
}
}
}
return path;

}

/* 歸約費用矩陣，返回費用矩陣的歸約常數 */
int Simplify(MATRIX* c)
{
int row, col, min_dist, h;
int n = c->citiesNumber;

h = 0;
/* 行歸約 */
for (row = 0; row < n; row++) {
/* 找出本行最小的元素 */
min_dist = INFINITY;
for (col = 0; col < n; col++) {
if (c->distance[row][col] < min_dist) {
min_dist = c->distance[row][col];
}
}
/* 如果本行元素都是無窮，說明本行已經被刪除 */
if (min_dist == INFINITY) continue;
/* 本行每元素減去最小元素 */
for (col = 0; col < n; col++) {
if (c->distance[row][col] != INFINITY) {
c->distance[row][col] -= min_dist;
}
}
/* 計算歸約常數 */
h += min_dist;
}

/* 列歸約 */
for (col = 0; col < n; col++) {
/* 找出本列最小的元素 */
min_dist = INFINITY;
for (row = 0; row < n; row++) {
if (c->distance[row][col] < min_dist) {
min_dist = c->distance[row][col];
}
}
/* 如果本列元素都是無窮，說明本列已經被刪除 */
if (min_dist == INFINITY) continue;
/* 本列元素減去最小元素 */
for (row = 0; row < n; row++) {
if (c->distance[row][col] != INFINITY) {
c->distance[row][col] -= min_dist;
}
}
/* 計算歸約常數 */
h += min_dist;
}
return (h);
}

/* 搜索所有花費為零的邊中最合適的，使左枝下界更大 */
EDGE SelectBestEdge(MATRIX c)
{
int row, col;
int n = c.citiesNumber;
int maxD;
EDGE best, edge;

/* 所用函數聲明 */
int D(MATRIX, EDGE);

maxD = 0;
for (row = 0; row < n; row++) {
for (col = 0; col < n; col++) {
edge.head = row;
edge.tail = col;
if (!c.distance[row][col] && maxD < D(c, edge)) {
maxD = D(c, edge);
best = edge;
}
}
}
return (best);
}

/* 計算如果選 edge 作為分枝邊，左枝（不含 edge）下界的增量 */
int D(MATRIX c, EDGE edge)
{
int row, col, dRow, dCol;
int n = c.citiesNumber;

dRow = INFINITY;
for (col = 0; col < n; col++) {
if (dRow < c.distance[edge.head][col] && col != edge.tail) {
dRow = c.distance[edge.head][col];
}
}
dCol = INFINITY;
for (row = 0; row < n; row++) {
if (dCol < c.distance[row][edge.tail] && row != edge.head) {
dCol = c.distance[row][edge.tail];
}
}
return (dRow + dCol);
}

/* 刪掉所選分枝邊 */
MATRIX LeftNode(MATRIX c, EDGE edge)
{
c.distance[edge.head][edge.tail] = INFINITY;
return c;
}

/* 刪除行列和迴路邊後的矩陣 */
MATRIX RightNode(MATRIX c, EDGE edge, PATH path)
{
int row, col;
int n = c.citiesNumber;
EDGE loopEdge;

/* 聲明所需要的求迴路邊函數 */
EDGE LoopEdge(PATH, EDGE);

for (col = 0; col < n; col++)
c.distance[edge.head][col] = INFINITY;
for (row = 0; row < n; row++)
c.distance[row][edge.tail] = INFINITY;

loopEdge = LoopEdge(path, edge);
c.distance[loopEdge.head][loopEdge.tail] = INFINITY;

return (c);
}

/* 計算迴路邊的函數
* 除了加入的新邊，當前結點路線集合中還可能包含一些已經選定的邊，這些邊構成一條或
* 幾條路徑，為了不構成迴路，必須使其中包含新邊的路徑頭尾不能相連，本函數返回這個
* 頭尾相連的邊，以便把這個迴路邊的長度設成無窮。
*/
EDGE LoopEdge(PATH path, EDGE edge)
{
int i, j;
EDGE loopEdge;

/* 最小的迴路邊 */
loopEdge.head = edge.tail;
loopEdge.tail = edge.head;

/* 尋找迴路邊的頭端點，即包含新邊的路徑的尾端點 */
for (i = 0; i < path.edgesNumber; i++) {
for (j = 0; j < path.edgesNumber; j++) {
if (loopEdge.head == path.edge[j].head) {
/* 擴大迴路邊 */
loopEdge.head = path.edge[j].tail;
break;
}
}
}
/* 尋找迴路邊的尾端點，即包含新邊的路徑的頭端點 */
for (i = 0; i < path.edgesNumber; i++) {
for (j = 0; j < path.edgesNumber; j++) {
if (loopEdge.tail == path.edge[j].tail) {
/* 擴大迴路邊 */
loopEdge.tail = path.edge[j].head;
break;
}
}
}

return (loopEdge);
}

/* 將新邊加入到路徑中 */
PATH AddEdge(EDGE edge, PATH path)
{
path.edge[path.edgesNumber++] = edge;
return path;
}

/* 計算花費矩陣當前階數 */
int MatrixSize(MATRIX c, PATH path)
{
return (c.citiesNumber - path.edgesNumber);
}

/* 顯示路徑 */
void ShowPath(PATH path, MATRIX c)
{
int i, dist;
EDGE edge;
int n = path.edgesNumber;

dist = 0;
printf("\nThe path is: ");
for (i = 0; i < n; i++) {
edge = path.edge[i];
printf("(%d, %d) ", edge.head + 1, edge.tail + 1);
dist += c.distance[edge.head][edge.tail];
}
/* printf("[Total Cost: %d]\n", dist); */
}

/* 顯示花費矩陣 */
void ShowMatrix(MATRIX c)
{
int row, col;
int n = c.citiesNumber;

for (row = 0; row < n; row++) {
for (col = 0; col < n; col++) {
if (c.distance[row][col] != INFINITY) {
printf("%3d", c.distance[row][col]);
}
else {
printf(" -");
}
}
putchar('\n');
}
getch();
}

⑽ 求如下有向圖的關鍵路徑以及任意兩點之間的最短距離

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

}

運行結果

c語言求任意兩點之間最短路徑

與c語言求任意兩點之間最短路徑相關的內容