数据结构与算法分析实验10 实现最短路径算法

1.上机名称

实现最短路径算法

2.上机要求

（1）用Dijkstra算法实现单源最短路径算法
（2）用Floyd算法实现多源最短路径算法

3.上机环境

visual studio 2022
Windows11 家庭版 64位操作系统

4.程序清单(写明运行结果及结果分析)

由于写的是可优化代码，在前面的实验里已经给出了许多基础，在下面的程序清单部分，只进行了部分代码的修改和添加，可以先参照前一篇博客内容进行理解。

4.1 程序清单

4.1.1 头文件 graph.h 内容如下：

修改头文件内容：进行添加的部分

#include<limits>
class Graph {
public:void ShortPath_DIJ(int firstid = 0);				//使用Dijkstra算法实现单源最短路径算法，仅在GKind == _NET || GKind == _GRAPH 时有效,过程中将无关当作距离为INT_MAX处理void ShortPath_Floyd();							//使用floyd算法求解多源最短路径，过程中将无关距离当作INT_MAX处理
};

4.1.2 实现文件 graph.cpp 内容如下：

函数printARR，实现邻接矩阵的打印：

void Graph::printARR(){std::cout << "图的邻接矩阵：\n";switch (GKind){case UN_GRAPH:case UN_NET: {for (int i = 0; i < vex_num; i++) {for (int j = 0; j < vex_num; j++) {std::cout << GArray[i][j] << "\t";}std::cout << std::endl;}break;}case _GRAPH:case _NET: {for (int i = 0; i < vex_num; i++) {for (int j = 0; j < vex_num; j++) {if (GArray[i][j] == 0 && i != j) {std::cout << "INF" << "\t";continue;}std::cout << GArray[i][j] << "\t";}std::cout << std::endl;}break;}default:std::cout << "Print Error!";exit(9);break;}
}

函数ShortPath_DIJ，DIJ算法实现最短路径

void Graph::ShortPath_DIJ(int firstid){if (GKind == UN_GRAPH || GKind == UN_NET) {	//排除无向图的情况std::cout << "DIJ算法仅支持有向图" << std::endl;exit(6);}//处理邻接矩阵int size = vex_num;int** tmp = new int* [size]; for (int i = 0; i < size; i++) tmp[i] = new int[size];for (int i = 0; i < size; i++) for (int j = 0; j < size; j++) { tmp[i][j] = GArray[i][j]; if (tmp[i][j] == 0 && i != j) tmp[i][j] = INT_MAX;}bool* S_Is_In = new bool[vex_num];		//标记列表，表示是否被选中int* S_All_Weight = new int[vex_num];	//列表，表示路径总权重for (int i = 0; i < vex_num; i++) {		//初始化S_Is_In[i] = false;					S_All_Weight[i] = tmp[firstid][i];	//firstid 到其他节点的距离先存到S_All_Weight里面}S_Is_In[firstid] = true;				//firstid 先入集合/*for (int i = 0; i < vex_num; i++)std::cout << S_All_Weight[i] << " ";std::cout << std::endl;*/for (int i = 0; i < vex_num-1 ; i++) {int min = 0; while (S_Is_In[min] == true)min++;	//找到第一个不在集合里的节点for (int t = min + 1; t < vex_num; t++) {		//找到权值最小的节点，下标为 minif (S_Is_In[t] != true && (S_All_Weight[t] < S_All_Weight[min])) min = t;}S_Is_In[min] = true;		//把j节点放进去//std::cout << min << " is in" << std::endl;for (int current = 0; current < vex_num; current++) {	//对每一个S_All_Weightif (S_Is_In[current] == false && S_All_Weight[min] + tmp[min][current] < S_All_Weight[current]&&tmp[min][current]!=INT_MAX&&S_All_Weight[min]!=INT_MAX) {//如果满足更新条件,注意INT_MAX的越位S_All_Weight[current] = S_All_Weight[min] + tmp[min][current];	//进行数据更新//std::cout << S_All_Weight[current] << "=" << S_All_Weight[min] << "+" << tmp[min][current] << std::endl;}}/*for (int i = 0; i < vex_num; i++)std::cout << S_All_Weight[i] << " ";std::cout << std::endl;*/}std::cout << "由DIJ算法，从下标为" << firstid << "的顶点出发，到达各个顶点距离的最小值为：" << std::endl;for (int i = 0; i < vex_num; i++)std::cout << i << ":" << S_All_Weight[i] << "  ";std::cout << std::endl;delete[]  S_All_Weight;delete[] S_Is_In;
}

函数ShortPath_Floyd，Floyd算法实现最短路径

void Graph::ShortPath_Floyd(){if (GKind == UN_GRAPH || GKind == UN_NET) {	//排除无向图的情况std::cout << "DIJ算法仅支持有向图" << std::endl;exit(8);}//处理邻接矩阵int size = vex_num;int** tmp = new int* [size]; for (int i = 0; i < size; i++) tmp[i] = new int[size];for (int i = 0; i < size; i++) for (int j = 0; j < size; j++) {tmp[i][j] = GArray[i][j];if (tmp[i][j] == 0 && i != j) tmp[i][j] = INT_MAX;}//核心算法int** S_Weight = new int* [size]; for (int i = 0; i < size; i++)S_Weight[i] = new int[size];//int** S_Path = new int* [size]; for (int i = 0; i < size; i++)S_Path[i] = new int[size];for (int i = 0; i < size; i++)for (int j = 0; j < size; j++) {S_Weight[i][j] = tmp[i][j]; //初始化最短路径}for (int w = 0; w < size; w++) {for (int i = 0; i < size; i++) {		//对于每一个方向的节点对for (int j = 0; j < size; j++) {	//都重复进行这样的判断if (S_Weight[i][w] + S_Weight[w][j] < S_Weight[i][j] && S_Weight[i][w] != INT_MAX && S_Weight[w][j] != INT_MAX) {S_Weight[i][j] = S_Weight[i][w] + S_Weight[w][j];}}}}std::cout << "由Floyd算法，得到图的最小路径矩阵为：" << std::endl;for (int i = 0; i < size; i++) {for (int j = 0; j < size; j++) {if (S_Weight[i][j] == INT_MAX) {std::cout << "INF" << "\t";continue;}std::cout << S_Weight[i][j] << "\t";}std::cout << std::endl;}//释放内存for (int i = 0; i < size; i++) {delete S_Weight[i];//delete S_Path[i];}delete[] S_Weight;//delete[] S_Path;
}

4.1.3 源文件 main.cpp 内容如下：

#include"Graph.h"
int main() {Graph g = Graph(6, _NET);g.link(0, 1, 1);g.link(0, 3, 5);g.link(0, 4, 2);g.link(1, 2, 2);g.link(1, 5, 1);g.link(2, 5, 1);g.link(2, 3, 1);g.link(3, 4, 1);g.link(4, 1, 2);g.link(4, 5, 1);g.link(5, 0, 10);g.printARR();g.ShortPath_DIJ(3);g.ShortPath_Floyd();
}

4.2 实现展效果示

以搭建下方图为例的实现效果，其中，以INF代替无穷大，理论与实际相符合：

5.上机体会

在实验里遇到了这样的问题：在INT_MAX上加上一个正数，变成负的很大的值，导致运行结果频频出错，在对循环内部的if判断函数加以限制之后，结果变得正常，这是由于计算机存储特性引起的bug，在实际工程里面需要引起注意。
Dijkstra算法是一种经典的求一个节点到其他节点最短路径的算法，但并不适合存在负权的图，Floyd算法是一种可以快速求出两节点之间最短路径的算法，但是并不适合存在负权环的图。尽管如此，算法的实际价值大于实现的过程，我们需要用起来，例如实际生活中的交通图，社会网络图，文献共引关系图等，都可以转化为图的相关问题并进行求解。