最短路徑算法集錦
/*
Name: 最短路徑算法集錦
Copyright:
Author: 巧若拙
Date: 12/11/14 15:32
Description:
列舉了深度優先搜索的遞歸和非遞歸算法，Dijkstra最短路徑算法，
基於Bellman-Fort最短路徑算法的改進型廣度優先搜索算法，
Floyd-Warshall最短路徑算法的原始版和變化版
本文是閱讀《啊哈！算法》後的學習筆記，代碼與教材中有些差異，若有錯誤請指正，謝謝！
測試數據：
5 7
0 3 2
0 4 9
4 2 1
4 1 3
2 1 1
3 4 2
3 1 8
*/
#include
#include
#define MAX 20 //最大頂點數量
#define MAXLEN 99999999 //最長路徑
int book[MAX] = {0}; //標記該城市是否已經在路徑中
int map[MAX][MAX] = {0};//鄰接矩陣存儲兩城市間路程
int min = MAXLEN; //城市間最短距離
int sum = 0;
int DeepSearchWay_1(int n, int startPos, int endPos);//深度優先搜索最短路徑驅動程序
void dfs(int n, int curPos, int endPos, int dis);//深度優先搜索最短路徑子程序
int DeepSearchWay_2(int n, int startPos, int endPos);//深度優先搜索最短路徑非遞歸算法
int Dijkstra(int n, int startPos, int endPos);//Dijkstra最短路徑算法
int bfs(int n, int startPos, int endPos);//改進的廣度優先搜索最短路徑算法
int Floyd(int n, int startPos, int endPos);//Floyd-Warshall最短路徑算法
int Floyd2(int n, int startPos, int endPos);//Floyd-Warshall最短路徑算法（原始版）
int Bellman(int n, int startPos, int endPos);//Bellman-Fort最短路徑算法
int main()
{
int i, j, m, n, a, b, c;
int startPos, endPos;
printf("請輸入城市數量：");
scanf("%d", &n);
printf("\n請輸入公路數量：");
scanf("%d", &m);
for (i=0; i
{
for (j=0; j
{
map[i][j] = (i == j) ? 0 : MAXLEN;
}
}
printf("\n請按照a b c格式輸入城市間的道路信息：\n");
for (i=0; i
{
scanf("%d%d%d", &a,&b,&c);
map[a][b] = c;
}
while (1)
{
printf("請輸入起點城市編號：");
scanf("%d", &startPos);
printf("請輸入終點城市編號：");
scanf("%d", &endPos);
min = DeepSearchWay_1(n, startPos, endPos);
printf("深度優先搜索1： %d->%d = %d\n", startPos, endPos, min);
min = DeepSearchWay_2(n, startPos, endPos);
printf("深度優先搜索2：%d->%d = %d\n", startPos, endPos, min);
min = Dijkstra(n, startPos, endPos);
printf("Dijkstra最短路徑算法：%d->%d = %d\n", startPos, endPos, min);
min = bfs(n, startPos, endPos);
printf("改進的廣度優先搜索：%d->%d = %d\n", startPos, endPos, min);
min = Floyd(n, startPos, endPos);
printf("Floyd-Warshall最短路徑算法：%d->%d = %d\n", startPos, endPos, min);
min = Floyd2(n, startPos, endPos);
printf("Floyd-Warshall最短路徑算法2：%d->%d = %d\n", startPos, endPos, min);
min = Bellman(n, startPos, endPos);
printf("Bellman-Fort最短路徑算法：%d->%d = %d\n", startPos, endPos, min);
}
return 0;
}
int DeepSearchWay_1(int n, int startPos, int endPos)//深度優先搜索最短路徑驅動程序
{
int i;
for (i=0; i
book[i] = 0;
sum = 0;
min = MAXLEN; //城市間最短距離
book[startPos] = 1;
dfs(n, startPos, endPos, 0);
printf("搜索次數為 %d\n", sum);
return min;
}
void dfs(int n, int curPos, int endPos, int dis)//深度優先搜索最短路徑子程序
{
int i;
if (dis > min) //當前路程已大於最短路程，直接返回
return ;
if (curPos == endPos)
{
if (dis < min)
min = dis;
return ;
}
for (i=0; i
{
if (book[i] == 0 && map[curPos][i] != MAXLEN)
{
book[i] = 1;
dfs(n, i, endPos, dis+map[curPos][i]);
book[i] = 0;
}
sum++;
}
}
int DeepSearchWay_2(int n, int startPos, int endPos)//深度優先搜索最短路徑非遞歸算法
{
int Vex[MAX] = {0};
int Stack[MAX] = {0};
int Dis[MAX] = {0};
int i, cur, top = 0;
int sum = 0;
for (i=0; i
book[i] = 0;
for (i=0; i
Dis[i] = map[startPos][i];
Stack[top] = startPos;
book[startPos] = 1;
while (top >= 0)
{
if (Vex[top] < n)
{
i = Vex[top];
cur = Stack[top];
if (book[i] == 0 && map[cur][i] != MAXLEN)
{
if (Dis[i] > Dis[cur] + map[cur][i]) //對各條邊進行松弛
{
Dis[i] = Dis[cur] + map[cur][i];
}
if (i != endPos)
{
Stack[++top] = i;
book[i] = 1; //接入路徑
Vex[top] = 0;
}
else
Vex[top]++;
}
else
{
Vex[top]++;
}
sum++;
}
else //退棧
{
book[Stack[top]] = 0; //離開路徑
top--;
if (top >= 0) //轉向下一條邊
{
Vex[top]++;
}
}
}
printf("搜索次數為 %d\n", sum);
return Dis[endPos];
}
int Dijkstra(int n, int startPos, int endPos)//Dijkstra最短路徑算法
{
int i, j, v, min;
int Dis[MAX] = {0};
int sum = 0;
for (i=0; i
book[i] = 0;
for (i=0; i
Dis[i] = map[startPos][i];
book[startPos] = 1;
for (j=1; j
{
min = MAXLEN; //城市間最短距離
v = startPos;
for (i=0; i
{
if (book[i] == 0 && Dis[i] < min)
{
min = Dis[i];
v = i;
}
sum++;
}
if (v == endPos) //已經找到最短路徑
break;
book[v] = 1;
for (i=0; i
{
if (map[v][i] != MAXLEN)
{
if (Dis[i] > Dis[v] + map[v][i])
Dis[i] = Dis[v] + map[v][i];
}
sum++;
}
}
printf("搜索次數為 %d\n", sum);
return Dis[endPos];
}
int bfs(int n, int startPos, int endPos)//改進的廣度優先搜索最短路徑算法
{
int i, k, front, rear;
int Dis[MAX] = {0};
int Queue[MAX] = {0};
int sum = 0;
for (i=0; i
book[i] = 0;
for (i=0; i
Dis[i] = MAXLEN;
Dis[startPos] = 0;
book[startPos] = 1;
front = rear = 0;
Queue[rear++] = startPos;
while (front != rear)
{
k = Queue[front];
for (i=0; i
{
if (Dis[i] > Dis[k] + map[k][i])
{
Dis[i] = Dis[k] + map[k][i];
if (book[i] == 0)//入隊列
{
Queue[rear] = i;
rear = (rear + 1) % MAX;
book[i] = 1;
}
}
sum++;
}
book[k] = 0;
front = (front + 1) % MAX;
}
printf("搜索次數為 %d\n", sum);
return Dis[endPos];
}
int Floyd(int n, int startPos, int endPos)//Floyd-Warshall最短路徑算法
{
int i, j, flag;
int Dis[MAX] = {0};
int sum = 0;
for (i=0; i
Dis[i] = map[startPos][i];
flag = 1;
while (flag)
{
flag = 0;
for (i=0; i
{
for (j=0; j
{
if (Dis[i] > Dis[j] + map[j][i])
{
Dis[i] = Dis[j] + map[j][i];
flag = 1;
}
sum++;
}
}
}
printf("搜索次數為 %d\n", sum);
return Dis[endPos];
}
int Floyd2(int n, int startPos, int endPos)//Floyd-Warshall最短路徑算法（原始版）
{
int i, j, k;
int Dis[MAX][MAX] = {0};
int sum = 0;
for (i=0; i
for (j=0; j
Dis[i][j] = map[i][j];
for (k=0; k
{
for (i=0; i
{
for (j=0; j
{
if (Dis[i][j] > Dis[i][k] + Dis[k][j])
{
Dis[i][j] = Dis[i][k] + Dis[k][j];
}
sum++;
}
}
}
printf("搜索次數為 %d\n", sum);
return Dis[startPos][endPos];
}
int Bellman(int n, int startPos, int endPos)//Bellman-Fort最短路徑算法
{
int i, j, m = 0;
int Dis[MAX] = {0};
int u[MAX*MAX] = {0};
int v[MAX*MAX] = {0};
int w[MAX*MAX] = {0};
int sum = 0;
for (i=0; i
{
for (j=0; j
{
if (i != j && map[i][j] != MAXLEN)
{
u[m] = i;
v[m] = j;
w[m++] = map[i][j];
}
}
}
for (i=0; i
Dis[i] = map[startPos][i];
for (i=1; i
{
for (j=0; j
{
if (Dis[v[j]] > Dis[u[j]] + w[j])
{
Dis[v[j]] = Dis[u[j]] + w[j];
}
sum++;
}
}
printf("搜索次數為 %d\n", sum);
return Dis[endPos];
}
