Bellman-Ford最短路径算法应用----城市间最短路径（包括负值）
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <stdbool.h>struct Dis{/*记录起点到每个顶点的最短路径信息*///string path;int weight;int pre;char path[100];}dis...
这篇博文不介绍Bellman-Ford的原理，很多文章都有分析。想了解原理的同学可以移步其他文章，这里仅做算法如何应用的介绍。
在最开始的时候，我找了很多有关该算法的文章，包括但不限于google、CSDN、Wikipedia、B站，但很多都是关于原理，没有具体应用，所以那时候很难理解这个算法。
Bellman-Ford算法可以应用到求负权图的情况，但也只能判断该图是否存在负环，如何处理这个负环，还是一个问题。由于要完成课设作业，所以还需要自己对这个算法进行改进。
编译环境：windows10 + VS2017
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct Dis
{
/*记录起点到每个顶点的最短路径信息*/
//string path;
int weight;
int pre;
char path[100];
}dis1[100];
int MAX = 9999;
int vexNum = 22;
int edgeNum = 86;
int u[100], v[100], w[100];
int info[44][3] = { {0,1,60},{2,3,-47},{4,5,161},{6,7,61},{8,9,-43},
{9,10,103},{10,11,63},{4,12,79},{13,14,92},{5,10,77},{2,0,39},{15,16,74},
{17,13,65},{3,1,76},{18,10,90},{11,19,82},{7,10,122},{19,3,63},{7,3,29},
{20,8,130},{1,5,145},{12,2,116},{10,20,139},{6,2,64},{13,12,140},
{11,18,-61},{14,0,135},{15,17,-28},{11,7,100},{13,4,-30},{10,6,129},
{9,20,116},{2,1,89},{16,13,154},{5,7,61},{4,6,56},{13,15,50},{7,19,74},
{0,3,55},{14,16,177},{2,7,53},{18,9,68},{6,13,20} };
int numofCity(char s1[50])
{
if (strcmp(s1, "York") == 0)
return 0;
else if (strcmp(s1, "Hull") == 0)
return 1;
else if (strcmp(s1, "Leeds") == 0)
return 2;
else if (strcmp(s1, "Doncaster") == 0)
return 3;
else if (strcmp(s1, "Liverpool") == 0)
return 4;
else if (strcmp(s1, "Nottingham") == 0)
return 5;
else if (strcmp(s1, "Manchester") == 0)
return 6;
else if (strcmp(s1, "Sheffield") == 0)
return 7;
else if (strcmp(s1, "Reading") == 0)
return 8;
else if (strcmp(s1, "Oxford") == 0)
return 9;
else if (strcmp(s1, "Birmingham") == 0)
return 10;
else if (strcmp(s1, "Leicester") == 0)
return 11;
else if (strcmp(s1, "Blackpool") == 0)
return 12;
else if (strcmp(s1, "Carlisle") == 0)
return 13;
else if (strcmp(s1, "Newcastle") == 0)
return 14;
else if (strcmp(s1, "Glasgow") == 0)
return 15;
else if (strcmp(s1, "Edinburgh") == 0)
return 16;
else if (strcmp(s1, "Moffat") == 0)
return 17;
else if (strcmp(s1, "Northampton") == 0)
return 18;
else if (strcmp(s1, "Lincoln") == 0)
return 19;
else if (strcmp(s1, "Bristol") == 0)
return 20;
else if (strcmp(s1, "Newcastle") == 0)
return 21;
}
void change_1()
{
FILE *fp1, *fp2;
int i = 0;
char s1[50], s2[50], s3[50];
int a1, a2;
char ch;
fp1 = fopen("energy.txt", "r");
fp2 = fopen("energy_02.txt", "w");
if (fp1 == NULL)
printf("open error£¡\n");
else if (fp2 == NULL)
printf("open error£¡\n");
else
{
while (fscanf(fp1, "%s\t%s\t%s", &s1, &s2, &s3) != EOF)
{
// fputc(ch,fp2);
a1 = numofCity(s1);
a2 = numofCity(s2);
fprintf(fp2, "%d\t%d\t%s\n", a1, a2, s3);
//putchar(ch);
// ch=fgetc(fp1);
//printf("%c",fgetc(fp1));
}
}
fclose(fp1);
fclose(fp2);
}
void bellman(int begin)
{
int temp = 0;
for (int i = 0; i < edgeNum / 2; i++)
{
u[temp] = info[i][0];
v[temp] = info[i][1];
w[temp] = info[i][2];
dis1[temp].weight = MAX;
temp++;
u[temp] = info[i][1];
v[temp] = info[i][0];
w[temp] = info[i][2];
dis1[temp].weight = MAX;
temp++;
}
for (int i = 0; i < vexNum; i++)
{
char ch1[20], ch2[20];
sprintf(ch1, "%d", begin);
sprintf(ch2, "%d", i);
if (i == begin)
{
strcat(dis1[i].path, "V");
strcat(dis1[i].path, ch1);
//printf("%s\n",dis1[i].path);
}
else
{
strcat(dis1[i].path, "V");
strcat(dis1[i].path, ch1);
strcat(dis1[i].path, "-->V");
strcat(dis1[i].path, ch2);
//printf("%s\n",dis1[i].path);
}
}
dis1[begin].weight = 0;
//printf("%d",dis1[begin].weight);
int count = 1;
//printf("%d",dis1[1].pre);
while (count != vexNum)
{
for (int i = 0; i < vexNum; i++)
{
int ch = 0;
bool isVisited[1000];
bool visited1 = false;
memset(isVisited, false, edgeNum);
for (int j = 0; j < edgeNum; j++)
{
char temp[100] = "";
if ((dis1[v[j]].weight > dis1[u[j]].weight + w[j]) && (isVisited[w[j]] != true) && (dis1[u[j]].pre != v[j]) && (dis1[u[j]].weight != MAX) && visited1 != true)
{
dis1[v[j]].weight = dis1[u[j]].weight + w[j];
isVisited[w[j]] = true;
ch = 1;
dis1[v[j]].pre = u[j];
//printf("%d\n",dis1[v[j]].pre);x1
char x[20];
sprintf(x, "%d", v[j]);
//strcat(dis1[u[j]].path, "-->V");
strcpy(temp, dis1[u[j]].path);
strcat(temp, "-->V");
strcat(temp, x);
//printf("%s\n", dis1[u[j]].path);
strcpy(dis1[v[j]].path,temp);
//printf("%s\n",dis1[v[j]].path);
if (w[j] == -43)
visited1 = true;
}
}
if (ch == 0)
break;
}
count++;
}
//printf("done");
//printf("%s %s",ch1,ch2);
}
void print(int begin)
{
char str[100] = "";
char x[20];
sprintf(x, "%d", begin);
strcat(str, "V");
strcat(str, x);
//printf("%s\n",str);
//printf("以%s为起点的图的最短路径为：",str);中文乱码
printf("the shortest path of %s is: \n", str);
//printf("%s\n",dis1[2].path);
for (int i = 0; i != vexNum; i++)
{
if (dis1[i].weight != MAX)
{
printf("%s = %i\n", dis1[i].path, dis1[i].weight);
//cout << dis1[i].path << "=" << dis1[i].weight << endl;
}
}
}
int main()
{
//change_1();
bellman(3);
print(3);
return 0;
}
运行结果（这是测试用例，主要是检查可以任意输出每两个城市间的路径和权重）
在完成了图的构建和算法的优化后，现在就要将城市和相隔距离填到图中，并做一些特殊化的处理。主要思路就是：**将每个城市任意顺序编号，然后存到数组，经过Bellman-Ford算法得到如上图的最短路径后，再对这些字符串做处理，输出每个结点编号代表的城市名。**这里也是程序的几大难点之一。
最开始拿到题目时，有几个问题一直困扰着我。
- 使用哪种数据结构来存储，怎样使用提供的energy.txt中的数据。
- 如何实现算法并对其进行优化，因为有少数城市间的距离为负，如何处理这个负值，避免负环情况的出现。
- 如何将得到的路径字符串转换为相应的城市名。
对于第一点，最后采用的是结构体，首先将城市名自定义成数字，然后存到数组中，通过数组对结构体进行初始化。最开始想的是直接对文件进行操作，但后来发现，从文件中读出来的数据为字符类型，还需要转化才能存到数组中，降低了程序的可读性，毕竟我们的重点不在这儿，所以放弃了这种方式。
对于第二点，每次负循环发生时，下一个将要访问的结点肯定是前面已经访问过的一个结点，所以在结构体中增加了pre这个属性，用于记录当前这个结点是从哪一个结点来的，从而能在if语句判断的时候，剔除掉这种情况。然后将每个负环只求一次，最后得到两个城市间的最短路径。
对于第三点，可以使用对字符串操作，依次遍历字节并进行对比，最后输出相应的城市名。
写在最后，**上面提到的各种情况，包括问题和解决方案，都是花费了大量时间调试得到的结果，所以希望你也这样。**关于注释的问题，由于最开始是中文写的注释，要交给学校，所以就删了。如果哪天有空我会更新注释。
完整代码在上面的基础上只有少许改动，如果你get到了我的idea，后面应该可以自己实现，如果有问题可以留言或者私信。
这里是整个项目的需求文档(英文版)、城市数据文件(energy.txt)、最后完成的代码(有需自取)。
运行结果截图：
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
0
0- 0
已为社区贡献1条内容
所有评论(0)