c語言實現最短路徑

A. 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;
}

B. 怎麼用c語言實現單源最短路徑問題要求是用Dijkstra演算法，最好寫出所有的代碼 ，包括結構定義等等，對一

C語言代碼：//清華大學出版社光碟的代碼
void ShortestPath_DIJ(MGraph G,int v0,PathMatrix &P,ShortPathTable &D)
{ // 演算法7.15
// 用Dijkstra演算法求有向網G的v0頂點到其餘頂點v的最短路徑P[v]
// 及其帶權長度D[v]。
// 若P[v][w]為TRUE，則w是衡辯嘩灶賀從v0到v當前求得最短路徑上的頂點。
// final[v]為TRUE當且僅當v∈S,即已經求得從v0到v的最短路徑。
int i=0,j, v,w,min;
bool final[MAX_VERTEX_NUM];
for (v=0; v<G.vexnum; ++v) {
final[v] = FALSE;
D[v] = G.arcs[v0][v].adj;
for (w=0; w<G.vexnum; ++w) P[v][w] = FALSE; // 設空路徑
if (D[v] < INFINITY) { P[v][v0] = TRUE; P[v][v] = TRUE; }
}
D[v0] = 0; final[v0] = TRUE; // 初始化，v0頂點屬於S集
//--- 開始主循環，每次求得v0到某個v頂點的最短路徑，並加v到S集 ---
for (i=1; i<G.vexnum; ++i) { // 其餘G.vexnum-1個頂點
min = INFINITY; // 當前所知離v0頂點的最近距離
for (w=0; w<G.vexnum; ++w)
if (!final[w]) // w頂點在V-S中
if (D[w]<min) { v = w; min = D[w]; } // w頂點離v0頂點更近
final[v] = TRUE; // 離v0頂點最近的咐行v加入S集
for (w=0; w<G.vexnum; ++w) // 更新當前最短路徑及距離
if (!final[w] && (min+G.arcs[v][w].adj<D[w])) {
// 修改D[w]和P[w], w∈V-S
D[w] = min + G.arcs[v][w].adj;
for(j=0;j<G.vexnum;j++) P[w][j] = P[v][j]; //第v行賦值於第w行
P[w][w] = TRUE; // P[w] = P[v]+[w]
}//if
}//for
} // ShortestPath_DIJ

C. 如何用C語言實現求迷宮的最短路徑

#include<stdio.h>
#include<stdlib.h>
#define M 8
#define N 8
#define Max 100
int mg[M+2][N+2]= //定義迷宮，0表示能走的塊，1表示不能走，在外圍加上一圈不能走的塊
{
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
struct
{
int i,j; //塊的位置
int pre; //本路徑中上一塊在隊列中的下標
}Qu[Max];
int front=-1,rear=-1;
void print(int n);
int mgpath(int xi,int yi,int xe,int ye) //搜索演算法
{
int i,j,find=0,di;
rear++;
Qu[rear].i=xi;
Qu[rear].j=yi;
Qu[rear].pre=-1;
mg[1][1]=-1;
while(front<=rear&&!find)
{
front++;
i=Qu[front].i;
j=Qu[front].j;
if(i==xe&&j==ye)
{
find=1;
print(front);
return(1);
}
for(di=0;di<4;di++)
{
switch(di) //四個方向
{
case 0:i=Qu[front].i-1;j=Qu[front].j;break;
case 1:i=Qu[front].i;j=Qu[front].j+1;break;
case 2:i=Qu[front].i+1;j=Qu[front].j;break;
case 3:i=Qu[front].i;j=Qu[front].j-1;break;
}
if(mg[i][j]==0)
{
rear++;
Qu[rear].i=i;
Qu[rear].j=j;
Qu[rear].pre=front;
mg[i][j]=-1; //避免死循環
}
}
}
return 0;
}

void print(int n) //輸出 路徑演算法
{
int k=n,j,m=1;
printf("\n");
do //將輸出的路徑上的所有pre改為-1
{
j=k;
k=Qu[k].pre;
Qu[j].pre=-1;
}while(k!=0);
printf("迷宮最短路徑如下：\n");
k=0;
while(k<Max)
{
if(Qu[k].pre==-1)
{
printf("\t(%d,%d)",Qu[k].i,Qu[k].j);
if(m%5==0)
printf("\n");
m++;
}
k++;
}
printf("\n");
}
int main()
{
mgpath(1,1,M,N);
system("pause");
return 0;
}

D. floyd演算法中輸出最短路徑序列的C語言代碼

floyd是動態規劃的簡化,所以輸出路徑一樣套用dp的典型記錄方式即可.
即,每次鬆弛時,記錄是鬆弛了哪一個點.然後輸出時遞歸輸出即可.
弄一個矩陣R[][]初始化為0,然後比如你的距離矩陣是D[][]
鬆弛改為是:
if(D[i][j] > D[i][k]+D[k][j]){
D[i][j] = D[i][k]+D[k][j];
R[i][j] = k;
}
輸出時可以寫一個遞歸函數
function out(a,b){
if(R[a][b] == 0){
return;
}
out(a,R[a][b]);
//輸出k
out(R[a][b],b);
}

E. C璇璦濡備綍瀹炵幇5涓鍩庡競涔嬮棿奼傛渶鐭璺寰勩 浠嶢鍑哄彂錛屾渶緇堝洖鍒癆銆 奼傛渶鐭璺寰勯棶棰樸 鍙鐢ㄧ┓涓炬潵瀹屾垚銆

//榪欎釜綆楁硶鍚嶅瓧鍙榪鏉版柉鐗規媺綆楁硶
#include<stdio.h>
#include<stdlib.h>
#definemax11000000000
inta[1000][1000];
intd[1000];//d琛ㄧず鏌愮壒瀹氳竟璺濈
intp[1000];//p琛ㄧず姘鎬箙杈硅窛紱
inti,j,k;
intm;//m浠ｈ〃杈規暟
intn;//n浠ｈ〃鐐規暟
intmain()
{
scanf("%d%d",&n,&m);
intmin1;
intx,y,z;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
a[x][y]=z;
a[y][x]=z;
}
for(i=1;i<=n;i++)
d[i]=max1;
d[1]=0;
for(i=1;i<=n;i++)
{
min1=max1;
for(j=1;j<=n;j++)
if(!p[j]&&d[j]<min1)
{
min1=d[j];
k=j;
}
p[k]=j;
for(j=1;j<=n;j++)
if(a[k][j]!=0&&!p[j]&&d[j]>d[k]+a[k][j])
d[j]=d[k]+a[k][j];
}
for(i=1;i<n;i++)
printf("%d->",p[i]);
printf("%d
",p[n]);
return0;
}