【经典算法实现 39】图的最短路径计算（优化Dijkstra算法支持负权计算 及 负环检测功能）（参考Bellman_Ford算法）
程序员文章站
2024-03-17 10:01:52
...
【经典算法实现 39】图的最短路径计算（优化Dijkstra算法支持负权计算 及 负环检测功能）（参考Bellman_Ford算法）
在前面《【经典算法实现 37】图的最短路径计算（Dijkstra迪杰斯特拉算法 及 其优化）》
我们实现了 Dijkstra迪杰斯特拉算法 对正权值图的计算，
本文参考 Bellman_Ford算法，实现对 Dijkstra迪杰斯特拉算法 的优化，让其支持：
- 负权值计算
- 负环检测 及 自动退出功能
一、核心算法实现
enum{None=0, Visited = 1, Wait = 2};
void Dijkstra(char c)
{
// 定义索引数组，用于索引每个节点在 dist[][] 数组中的位置 ，该数组从1开始计数，index[x]-1 为x的索引号
char cur, index[Node_Num], visit[Node_Num], visit_num=0, break_flag=0, i, j, k=0;
// 初始化访问数组为None
for(i=0; i<Node_Num; i++){
index[i] = 0;
visit[i] = None;
}
// 定义二维数组，用于保存每个节点到A 的最短距离，及其 上一个节点
int dist[Node_Num][3];
// 初始化数组
for(i = 0; i<Node_Num; i++)
{
dist[i][0]=0; // 当前节点字符
dist[i][1]=INT_MAX; // 当前节点到A 的最短距离
dist[i][2]=0; // 上一节点字符
}
// 初始化起始点
cur = c; // 记录起始点为第一个元素
index[cur-'A'] = visit_num + 1; // 更新索引数组
dist[ index[cur-'A']-1 ][0] = cur; // 当前节点字符
dist[ index[cur-'A']-1 ][1] = 0; // 当前节点到A 的最短距离
dist[ index[cur-'A']-1 ][2] = cur; // 上一节点字符
visit_num++;
// break_flag 标志dist 数组内容不再改变，此时 Dijkstra算法计算结束
while(!(cur==0 && break_flag>=Node_Num)){
if(cur == 0)// 新的一轮开始了
{
//清空 visit数组
// 初始化访问数组为None
for(i=0; i<Node_Num; i++){
visit[i] = None;
}
cur = c;
k++; // 如果 k > Node_Num，说明当前存在负环，计算失败
}
visit[cur-'A'] = Visited; // 标志当前节点已访问过
//查找所有与该节点相边的节点
for(i = 0; i<Node_Num; i++){
// 判断当前节点的值是否非法
if(sNode[cur-'A'][i] != INT_MAX){
// 如果当前节点未访问过
if(index[i] == 0){
index[i] = visit_num+1;
visit_num++;
}
visit[i] = visit[i]==Visited ? Visited : Wait;
// 判断当前节点的值是否需要更新
if(dist[index[i]-1][1] == INT_MAX || sNode[cur-'A'][i] + dist[index[cur-'A']-1][1] < dist[index[i]-1][1])
{
break_flag = 0;
dist[index[i]-1][0] = i + 'A';
dist[index[i]-1][1] = sNode[cur-'A'][i] + dist[index[cur-'A']-1][1];
dist[index[i]-1][2] = cur;
//printf("更新%c 的值为%3d， 计算 %3d + %3d = %3d\n", dist[index[i]-1][0],dist[index[i]-1][1], sNode[cur-'A'][i], dist[index[cur-'A']-1][1], dist[index[i]-1][1]);
}else{
break_flag++;
//printf("保持%c 的值为%3d， 计算 %3d + %3d = %3d", dist[index[i]-1][0], dist[index[i]-1][1], sNode[cur-'A'][i], dist[index[cur-'A']-1][1], sNode[cur-'A'][i] + dist[index[cur-'A']-1][1]);
//printf(" break_flag=%d\n", break_flag);
}
}
}
//从待访问数组中取一个待访问的起始点
for(i =0, cur=0; i<Node_Num; i++){
if(visit[i] == Wait){
//printf("\n查找到 %c(%d)=%d ", i+'A', i, visit[i]);
cur = i+ 'A';
break; // 退出循环
}
}
// 这一轮遍历结束，打印当前最短距离
if(cur ==0 )
{
printf("\n\nDijkstra算法查找%c的最短路径结束,打印表格\n",c);
for(i = 0; i<Node_Num; i++)
printf("%c ", dist[i][0]);
printf("\n");
for(i = 0; i<Node_Num; i++){
if(dist[i][1] == INT_MAX)break;
printf("%-2d ", dist[i][1]);
}
printf("\n");
for(i = 0; i<Node_Num; i++)
printf("%c ", dist[i][2]);
printf("\n\n");
}
if(k > Node_Num)
{
printf("存在负权环, 计算失败\n");
break;
}
}
}
二、运行结果：负权计算
输入为：
const int s_char[sNode_Num][3]={
{'A','B', 3}, {'A','C', -3},
{'B','D', -1}, {'B','A', 5},
{'C','D', 2},
{'D','E', -6}, {'D','F', 4},
{'E','G', -1},
{'F','C', -1}};
计算结果为：
网矩阵创建完毕
A B C D E F G
A . 3 -1 . . . .
B -2 . . -1 . . .
C . . . 2 . . .
D . . . . -6 4 .
E . . . . . . -1
F . . -1 . . . .
G . . . . . . .
Dijkstra算法查找A的最短路径结束,打印表格
A B C D E F G
0 3 -1 1 -5 5 -6
A A A C D D E
Dijkstra算法查找A的最短路径结束,打印表格
A B C D E F G
0 3 -1 1 -5 5 -6
A A A C D D E
三、运行结果：带负环计算
根据Bellman_Ford算法原理，如果最大处理次数为 m-1次，如果超过这个值，就说明存在负环。
如下图，很明显，C->D->F 之间存在负环
输入为：
const int s_char[sNode_Num][3]={
{'A','B', 3}, {'A','C', -3},
{'B','D', -1}, {'B','A', 5},
{'C','D', 2},
{'D','E', -6}, {'D','F', 4},
{'E','G', -1},
{'F','C', -10}};
运行结果为：
网矩阵创建完毕
A B C D E F G
A . 3 -3 . . . .
B 5 . . -1 . . .
C . . . 2 . . .
D . . . . -6 4 .
E . . . . . . -1
F . . -10 . . . .
G . . . . . . .
Dijkstra算法查找A的最短路径结束,打印表格
A B C D E F G
0 3 -7 -1 -7 3 -8
A A F C D D E
Dijkstra算法查找A的最短路径结束,打印表格
A B C D E F G
0 3 -11 -5 -11 -1 -12
A A F C D D E
Dijkstra算法查找A的最短路径结束,打印表格
A B C D E F G
0 3 -15 -9 -15 -5 -16
A A F C D D E
Dijkstra算法查找A的最短路径结束,打印表格
A B C D E F G
0 3 -19 -13 -19 -9 -20
A A F C D D E
Dijkstra算法查找A的最短路径结束,打印表格
A B C D E F G
0 3 -23 -17 -23 -13 -24
A A F C D D E
Dijkstra算法查找A的最短路径结束,打印表格
A B C D E F G
0 3 -27 -21 -27 -17 -28
A A F C D D E
Dijkstra算法查找A的最短路径结束,打印表格
A B C D E F G
0 3 -31 -25 -31 -21 -32
A A F C D D E
Dijkstra算法查找A的最短路径结束,打印表格
A B C D E F G
0 3 -35 -29 -35 -25 -36
A A F C D D E
存在负权环, 计算失败
请按任意键继续. . .
四、完整代码
#include <stdio.h>
#define Node_Num 7 // 顶点的数量
char pNode[Node_Num]={'A', 'B', 'C', 'D', 'E', 'F', 'G'}; // 用于保存顶点的值
int sNode[Node_Num][Node_Num]; // 用于表示各边的关系
#define INT_MAX 32767
#define sNode_Num 9 // 9条边
const int s_char[sNode_Num][3]={
{'A','B', 3}, {'A','C', -1},
{'B','D', -1}, {'B','A', -2},
{'C','D', 2},
{'D','E', -6}, {'D','F', 4},
{'E','G', -1},
{'F','C', -1}};
void Print_Matrix(void)
{
int start,end;
printf(" ");
for(start = 0; start<Node_Num; start++)
printf("%c ", pNode[start]);
for(start = 0; start<Node_Num; start++){
printf("\n%c ", pNode[start]);
for(end = 0; end<Node_Num; end++){
if(sNode[start][end] == INT_MAX)
printf(" . ");
else
printf("%2d ", sNode[start][end]);
}
}
printf("\n\n");
}
void Create_Matrix()
{
int i = 0, j=0, start, end;
//memset(sNode, INT_MAX, sizeof(sNode)); //初始化所有边为最大
for(i=0; i<sNode_Num; i++)
for(j=0; j<sNode_Num; j++)
sNode[i][j] = INT_MAX;
for(i = 0; i<sNode_Num; i++){
// 获取当前边的起始点
start = s_char[i][0] - 'A';
end = s_char[i][1] - 'A';
sNode[start][end] = s_char[i][2];
}
printf("网矩阵创建完毕\n\n");
}
enum{None=0, Visited = 1, Wait = 2};
void Dijkstra(char c)
{
// 定义索引数组，用于索引每个节点在 dist[][] 数组中的位置 ，该数组从1开始计数，index[x]-1 为x的索引号
char cur, index[Node_Num], visit[Node_Num], visit_num=0, break_flag=0, i, j, k=0;
// 初始化访问数组为None
for(i=0; i<Node_Num; i++){
index[i] = 0;
visit[i] = None;
}
// 定义二维数组，用于保存每个节点到A 的最短距离，及其 上一个节点
int dist[Node_Num][3];
// 初始化数组
for(i = 0; i<Node_Num; i++)
{
dist[i][0]=0; // 当前节点字符
dist[i][1]=INT_MAX; // 当前节点到A 的最短距离
dist[i][2]=0; // 上一节点字符
}
// 初始化起始点
cur = c; // 记录起始点为第一个元素
index[cur-'A'] = visit_num + 1; // 更新索引数组
dist[ index[cur-'A']-1 ][0] = cur; // 当前节点字符
dist[ index[cur-'A']-1 ][1] = 0; // 当前节点到A 的最短距离
dist[ index[cur-'A']-1 ][2] = cur; // 上一节点字符
visit_num++;
// break_flag 标志dist 数组内容不再改变，此时 Dijkstra算法计算结束
while(!(cur==0 && break_flag>=Node_Num)){
if(cur == 0)// 新的一轮开始了
{
//清空 visit数组
// 初始化访问数组为None
for(i=0; i<Node_Num; i++){
visit[i] = None;
}
cur = c;
k++; // 如果 k > Node_Num，说明当前存在负环，计算失败
}
visit[cur-'A'] = Visited; // 标志当前节点已访问过
//查找所有与该节点相边的节点
for(i = 0; i<Node_Num; i++){
// 判断当前节点的值是否非法
if(sNode[cur-'A'][i] != INT_MAX){
// 如果当前节点未访问过
if(index[i] == 0){
index[i] = visit_num+1;
visit_num++;
}
visit[i] = visit[i]==Visited ? Visited : Wait;
// 判断当前节点的值是否需要更新
if(dist[index[i]-1][1] == INT_MAX || sNode[cur-'A'][i] + dist[index[cur-'A']-1][1] < dist[index[i]-1][1])
{
break_flag = 0;
dist[index[i]-1][0] = i + 'A';
dist[index[i]-1][1] = sNode[cur-'A'][i] + dist[index[cur-'A']-1][1];
dist[index[i]-1][2] = cur;
//printf("更新%c 的值为%3d， 计算 %3d + %3d = %3d\n", dist[index[i]-1][0],dist[index[i]-1][1], sNode[cur-'A'][i], dist[index[cur-'A']-1][1], dist[index[i]-1][1]);
}else{
break_flag++;
//printf("保持%c 的值为%3d， 计算 %3d + %3d = %3d", dist[index[i]-1][0], dist[index[i]-1][1], sNode[cur-'A'][i], dist[index[cur-'A']-1][1], sNode[cur-'A'][i] + dist[index[cur-'A']-1][1]);
//printf(" break_flag=%d\n", break_flag);
}
}
}
//从待访问数组中取一个待访问的起始点
for(i =0, cur=0; i<Node_Num; i++){
if(visit[i] == Wait){
//printf("\n查找到 %c(%d)=%d ", i+'A', i, visit[i]);
cur = i+ 'A';
break; // 退出循环
}
}
// 这一轮遍历结束，打印当前最短距离
if(cur ==0 )
{
printf("\n\nDijkstra算法查找%c的最短路径结束,打印表格\n",c);
for(i = 0; i<Node_Num; i++)
printf("%c ", dist[i][0]);
printf("\n");
for(i = 0; i<Node_Num; i++){
if(dist[i][1] == INT_MAX)break;
printf("%-2d ", dist[i][1]);
}
printf("\n");
for(i = 0; i<Node_Num; i++)
printf("%c ", dist[i][2]);
printf("\n\n");
}
if(k > Node_Num)
{
printf("存在负权环, 计算失败\n");
break;
}
}
}
int main()
{
// 创建网矩阵
Create_Matrix();
// 打印网矩阵
Print_Matrix();
Dijkstra('A');
printf("\n\n");
return 0;
}