最短路径算法集锦 - c++编程基础

/*
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; //离开

最短路径算法集锦(一)