A. 如何用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;
}
B. 數據結構：求最短路徑，狄傑斯徹拉演算法的原理是什麼最好畫個圖詳解，謝謝！
以上圖為例進行說明，圖示是尋找從V1到V5的最短路徑的過程。
首先，將除起點V1以外所有頂點的路徑長度設為無窮大，其自身路徑長度為0；
1.將起點V1加入已求解的頂點集；
2.檢查新增的頂點的所有邊，若另一頂點不在已求解頂點集內，則將其路徑長度進行更新。新的路徑長度為其原長與新增頂點自身路徑長度加上邊長中的較小者；
3.從所有不在已求解頂點集的頂點中，選擇一個路徑長度最短的頂點，加入已求解頂點集，如果這個頂點是目標頂點，則求解結束，否則跳到第2步繼續求解。
圖中的例子，先加了V1，然後更新V2，V3，V6的長度分別為7，9，14；
然後加最近的V2，再更新V3，V4的長度，V3經V2到達比直接從V1出發要長，所以其值沒有變化，V4的長度更新為22，以後的步驟類似，不再詳述。
C. 【數據結構】最短路徑之迪傑斯特拉(Dijkstra)演算法與弗洛伊德(Floyd)演算法
迪傑斯特拉(Dijkstra)演算法核心： 按照路徑長度遞增的次序產生最短路徑。
迪傑斯特拉(Dijkstra)演算法步驟：（求圖中v0到v8的最短路徑）並非一下子求出v0到v8的最短路徑，而是 一步一步求出它們之間頂點的最短路徑 ，過過程中都是 基於已經求出的最短路徑的基礎上，求得更遠頂點的最短路徑，最終得出源點與終點的最短路徑 。
弗洛伊德(Floyd)演算法是一個經典的 動態規劃演算法 。