㈠ c語言最短路徑問題。
#include <stdio.h>
#define N 7 /* 頂點數目 */
#define I 999 /* 表示無窮大 */
int graph[N][N] = { /* 圖的鄰接矩陣 */
{I, 4, 5, 8, I, I, I},
{I, I, I, 6, 6, I, I},
{I, I, I, 5, I, 7, I},
{I, I, I, I, 8, 9, 9},
{I, I, I, I, I, I, 5},
{I, I, I, I, I, I, 4},
{I, I, I, I, I, I, I}
};
int List[N]; /* 存放拓撲序列 */
int TopologicalOrder(); /* 拓撲排序函數 */
void main() /* 主 函 數 */
{
int i, j, k, l;
int ee[N], el[N]; /* 最長最短距離 */
int path_e[N][N], path_l[N][N], n_e[N], n_l[N]; /* 記錄路徑數據 */
/* 初始化數據 */
for (i = 0; i < N; i++) {
n_e[i] = 0; /* 到 i 的最短路線的結點數 */
n_l[i] = 0; /* 到 i 的最長路線的結點數 */
ee[i] = I;
el[i] = 0;
}
ee[0] = el[0] = 0; /* 初始化頭結點 */
path_e[0][0] = 0;
path_l[0][0] = 0;
n_e[0] = 1;
n_l[0] = 1;
/* 拓撲排序 */
if (!TopologicalOrder())
return;
/* 對於拓撲序列,運用動態規劃步步算出最長路線與最短路線 */
for (i = 0; i < N; i++) {
/* 提取拓撲序列的元素 */
k = List[i];
/* 更新它所指向頂點的所有數據 */
for (j = 0; j < N; j++) {
/* 尋找指向的頂點 */
if (graph[k][j] != I) {
/* 如果新路徑更短 */
if (graph[k][j] + ee[k] < ee[j]) {
/* 更新最短路徑長度 */
ee[j] = graph[k][j] + ee[k];
/* 更新最短路線 */
for (l = 0; l < n_e[k]; l++) {
path_e[j][l] = path_e[k][l];
}
path_e[j][l] = j;
n_e[j] = l + 1;
}
/* 如果新路徑更長 */
if (graph[k][j] + el[k] > el[j]) {
/* 更新最長路徑長度 */
el[j] = graph[k][j] + el[k];
/* 更新最長路線 */
for (l = 0; l < n_l[k]; l++) {
path_l[j][l] = path_l[k][l];
}
path_l[j][l] = j;
n_l[j] = l + 1;
}
}
}
}
/* 輸出結果到屏幕 */
for (i = 0; i < N; i++) {
printf("shortest(%d): %2d Path: ", i + 1, ee[i]);
for (j = 0; j < n_e[i]; j++) {
printf("%d ", path_e[i][j] + 1);
}
printf("\n");
printf("longest (%d): %2d Path: ", i + 1, el[i]);
for (j = 0; j < n_l[i]; j++) {
printf("%d ", path_l[i][j] + 1);
}
printf("\n");
}
}
int TopologicalOrder()
{
int i, j, top, count;
int indegree[N], Stack[N];
top = 0; /* 棧頂標志 */
for (i = 0; i < N; i++) {
indegree[i] = 0; /* 初始化入度 */
for (j = 0; j < N; j++) {
if (graph[j][i] != I) { /* 如連通 */
indegree[i]++; /* 入度自增1 */
}
}
if (!indegree[i]){ /* 如入度為零 */
Stack[top++] = i; /* 入棧 */
}
}
count = 0; /* 輸出頂點數 */
while (top != 0) {
i = Stack[--top];
List[count++] = i;
for (j = 0; j < N; j++) {
if (graph[i][j] != I) { /* 如連通 */
if (!(--indegree[j])) { /* 而且入度為零 */
Stack[top++] = j; /* 入棧 */
}
}
}/* for */
}/* while */
return (count < N) ? 0 : 1;
}
㈡ 嚴蔚敏的數據結構（C語言版）最短路徑演算法 代碼段：p[w]=p[v];p[w][w]=true;//p[w]=p[v]+[w]是什麼意思
二維數組P中保存的是v0到各個點的最短路徑。在v行中，值為true的列連起來，就是v0到v的最短路徑。因為v0到w點的最短路徑是v0到v的最短路徑在加上<v,w>，所以w列先復制所有的v列的值，然後在將p[w][w]=true。此時w行中所有值為true列，就是v0到w的最短路徑
㈢ 如何用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;
}
㈣ 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;
}