XI`AN TECHNOLOGICAL UNIVERSITY

课程设计报告

实验课程名称算法与数据结构

专业：

班级：

姓名：

学号：

实验学时：

指导教师：

成绩：

2023 年 1 月 7 日

一、实验报告

一、绪论

二、基本要求

三、信息描述

五、详细设计

六、调试与测试：

八、总结

源码：

视频上传比较麻烦，需要的同学可以联系我

一、实验报告

一、绪论

迪杰特斯拉算法思想：

设G=（V,E）是一个带权有向图，把顶点集合V分成两组，求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径，就将加入到集合S中。直到全部顶点都加入到S中，算法就结束了）。第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点V到S中各顶点的最短路径长度大于从源点V到V中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从V到此顶点的最短路径长度，V中的顶点的距离是从V到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

二、基本要求

(1)设计最短路径，包含以下方面：

1、用邻接矩阵存储一张带权有向图。

2、对图进行从某一源点到其他各顶点的最短路径

3、输出最后结果（路径名称、路径长度）。

三、信息描述

邻接矩阵建立包括：用二维数组存储信息。没有直达路径的为无穷。

用循环来判断最小值。

最终结果用一维数组存储。D[]存放源点到其他顶点的最短路径的长度，P[]存放该顶点最短路径的前驱顶点下标，visit[]为访问标识。初始全部值设为F，先把源点的标识设为T，后面每找到一个源点到其余顶点的最短路径，就将该顶点下标对应的标识置为T。直到全部顶点执行完毕。

输出一维数组D[]和P[]，显示最终结果。

总体设计

五、详细设计

第一部分，进行对邻接矩阵的初始化，首先自己到自己的距离肯定为0，然后到其余结点初始化为MAX，然后通过一个for循环，对边进行数据存入，打印函数用来验证。

第二部分对于结点类的创建（构造、拷贝构造、赋值运算符重载、比较方式的重载）类中存放每一个结点的下标、最短路径长度、前驱结点。

第三部分：打印结果函数

迪杰斯特拉算法部分（核心）

完成好邻接矩阵的初始化工作以后，输入我们的起点坐标，对于起点来说，从起点到达起点的距离肯定是0，然后将起点坐标置入优先队列中，进入循环，循环退出条件是优先队列为空

每次取堆顶元素，使用cur进行保存，之后就将此结点pop

利用cur找出所有可以从cur出发到达的所有结点，将这些结点保存到集合S中，对于集合中的所有结点进行：

newlength = node[Index]._length + Graph[Index][back];

// 如果新距离小于cur之前的最小距离，就将cur重新赋值，并入队列

if (newlength < node[back]._length)

{

node[back]._length = newlength;

node[back]._prev = Index;

q.push(node[back]);

}

六、调试与测试：

在我写代码的时候大部分问题都可以查资料解决，如何使用vector,如果使用优先级队列，以及思路的来源也是借助于网上的资料查看，视频讲解，耗费时间最多的应该就是对于自定义类型优先级队列第三个参数比较方式的确定，本来我的代码是这样通过结构体与函数指针来实现，不过也出现了类型不匹配的问题，最后通过使用类中对比较关系的重载写出了bool类型关于>符号的重载（因为要建大堆）。

七、程序清单和执行结果：清单中应有足够的注释

运行结果：

源码：

//(1)设计最短路径，包含以下方面:

//1、用邻接矩阵存储一张带权有向图。

//2、对图进行从某一源点到其他各顶点的最短路径

//了、输出最后结果(路径名称、路径长度)。

//三、信息描述

//邻接矩阵建立包括 : 用二维数组存储信息。没有直达路径的为无

//穷

//用循环来判断最小值

//最终结果用一维数组存储。D[]存放源点到其他顶点的最短路径的

//长度，P[]存放该顶点最短路径的前驱顶点下标

// 0 1 2 0 4 10 1 2 3 1 4 7 2 0 4 2 3 4 3 4 5 4 2 3

#include<functional>

#include<stdlib.h>

#include<iostream>

using namespace std;

#include<vector>

#include<queue>

#define MAX 1000 // 不可到达

int V, E, S; // 顶点数、边数、起点

vector<vector<int>> Graph;

void CreatMyGraph() // 初始化邻接矩阵

{

cout << "请输入顶点数、边数" << endl;

cin >> V >> E;

Graph.resize(V);

for (int i = 0; i < V; i++)

{

Graph[i].resize(V);

for (int j = 0; j < V; j++)

{

if (i == j)

Graph[i][j] = 0; // 自己到自己赋值为0

else

Graph[i][j] = MAX; // 默认初始化到其余顶点均为MAX

}

/*Graph[0][1] = 2;

Graph[0][3] = 1;

Graph[1][3] = 3;

Graph[1][4] = 7;

Graph[2][0] = 4;

Graph[3][2] = 2;

Graph[3][4] = 2;

Graph[3][5] = 8;

Graph[3][6] = 4;

Graph[4][6] = 1;

Graph[6][5] = 1;

Graph[2][5] = 5;*/

int begin, end;

int length;

for (int i = 0; i < E; i++)

{

cout << "请输入第" << i + 1 << "条边的起点、终点、权值：" << endl;

cin >> begin >> end >> length;

Graph[begin][end] = length; // 初始化邻接矩阵

}

void PrintMyGraph()

{

cout << "图的邻接矩阵存储为：" << endl;

for (int i = 0; i < V; i++)

{

for (int j = 0; j < V; j++)

{

cout << Graph[i][j] << " ";

}

cout << endl;

}

//typedef struct DjNode

//{

// int _index;

// int _length;

// int _prev;

//}Node;

//Node BuyNode(int index, int length)

//{

// Node* newnode = (Node*)malloc(sizeof(Node));

// newnode->_index = index;

// newnode->_length = length;

// newnode->_prev = 0;

// return newnode;

//}

//typedef bool (*PCOM)(const Node& left, const Node& right);

//bool Compare(const Node left, const Node right)

//{

// return left._length > right._length;

//}

class Node

{

public:

Node(int index, int length, int prev)

: _index(index)

, _length(length)

, _prev(prev)

{}

Node(const Node& d)

{

_index = d._index;

_length = d._length;

_prev = d._prev;

}

Node& operator=(const Node& node)

{

if (this != &node)

{

_index = node._index;

_length = node._length;

_prev = node._prev;

}

return *this;

}

bool operator>(const Node& d)const

{

return _length > d._length;

}

bool operator<(const Node& d)const

{

return _length < d._length;

}

int _index;

int _length;

int _prev;

};

class Com

{

public:

bool operator()(const Node&left, const Node&right)const

{

return left._length > right._length;

}

};

void Print_output(int start, vector<Node> node)

{

cout << "由" << start << "到其余各顶点距离分别为" << endl;

for (int i = 0; i < V; i++)

{

if (i == start)

continue;

else

cout << start << "->" << i << ": " << node[i]._length << endl;

}

void Dijkstra_Algorithm()

{

// 1、初始化输出数组D、P

//vector<int> D(V, MAX); // 初始化最短长度数组D

//vector<int> P(V, 0); // 初始化前驱结点数组P

vector<Node> node(V, Node(0,0,0));

for (int i = 0; i < V; i++)

{

//node[i] = BuyNode(i, MAX); // 结点初始化

node[i]._index = i;

node[i]._length = MAX;

node[i]._prev = 0;

}

// 2、初始化顶点D[S]

cout << "请输入起点" << endl;

cin >> S;

node[S]._length = 0;

// 3、创建优先队列，起点元素入队列

priority_queue<Node, vector<Node>, greater<Node>> q;

q.push(node[S]);

while (!q.empty())

{

Node cur = q.top();

q.pop(); // 取出堆顶元素并进行保存

vector<int> pre_next;

int Index = cur._index;

for (int i = 0; i < V; i++) // 将所有可以一步到达当前结点的元素下标全部保存到pre_next中

{

if (Graph[Index][i] > 0 && Graph[Index][i] != MAX)

pre_next.push_back(i);

}

while (!pre_next.empty()) // 对于每一个可以到达cur的结点

{

int back = pre_next.back(); //访问一个取出一个

pre_next.pop_back();

// 新距离就为从源点到back距离加上 back到cur的距离

int newlength = node[Index]._length + Graph[Index][back];

// 如果新距离小于cur之前的最小距离，就将cur重新赋值，并入队列

if (newlength < node[back]._length)

{

node[back]._length = newlength;

node[back]._prev = Index;

q.push(node[back]);

}

cout << endl;

Print_output(S, node);

}

void _Dijkstra_Algorithm()

{

cout << "Dijkstra_Algorithm :" << endl;

int choice;

while (1)

{

cout << "请输入：" << "[1]开始" << "[0]结束" << endl;

cin >> choice;

switch (choice)

{

case 1:

Dijkstra_Algorithm();

break;

case 0:

exit(0);

break;

}

int main()

{

int choice;

while (1)

{

cout << "*******************************************" << endl;

cout << "***************请输入请求：****************" << endl;

cout << "***************[1]初始化数据***************" << endl;

cout << "***************[2]迪杰斯特拉算法***********" << endl;

cout << "***************[0]退出*********************" << endl;

cout << "*******************************************" << endl;

cin >> choice;

switch (choice)

{

case 1:

CreatMyGraph();

break;

case 2:

_Dijkstra_Algorithm();

break;

case 0:

exit(0);

break;

default:

cout << "输入错误,请重新输入" << endl;

break;

}

return 0;

}

八、总结

通过这次课设，进一步提高了对于数据结构的认知，提升了自己的编程能力，了解了迪杰斯特拉算法在使用优先级队列来解决问题的便利之处。

源码：

//(1)设计最短路径，包含以下方面:
//1、用邻接矩阵存储一张带权有向图。
//2、对图进行从某一源点到其他各顶点的最短路径
//了、输出最后结果(路径名称、路径长度)。
//三、信息描述
//邻接矩阵建立包括 : 用二维数组存储信息。没有直达路径的为无
//穷
//用循环来判断最小值
//最终结果用一维数组存储。D[]存放源点到其他顶点的最短路径的
//长度，P[]存放该顶点最短路径的前驱顶点下标
// 0 1 2   0 4 10  1 2 3  1 4 7  2 0 4  2 3 4  3 4 5  4 2 3
#include<functional>
#include<stdlib.h>
#include<iostream>
using namespace std;
#include<vector>
#include<queue>
#define MAX 1000 // 不可到达
int V, E, S; // 顶点数、边数、起点vector<vector<int>> Graph;void CreatMyGraph() // 初始化邻接矩阵
{cout << "请输入顶点数、边数" << endl;cin >> V >> E;Graph.resize(V);for (int i = 0; i < V; i++){Graph[i].resize(V);for (int j = 0; j < V; j++){if (i == j)Graph[i][j] = 0;	// 自己到自己赋值为0elseGraph[i][j] = MAX;	// 默认初始化到其余顶点均为MAX}}/*Graph[0][1] = 2;Graph[0][3] = 1;Graph[1][3] = 3;Graph[1][4] = 7;Graph[2][0] = 4;Graph[3][2] = 2;Graph[3][4] = 2;Graph[3][5] = 8;Graph[3][6] = 4;Graph[4][6] = 1;Graph[6][5] = 1;Graph[2][5] = 5;*/int begin, end;int	length;for (int i = 0; i < E; i++){cout << "请输入第" << i + 1 << "条边的起点、终点、权值：" << endl;cin >> begin >> end >> length;Graph[begin][end] = length;	// 初始化邻接矩阵}
}void PrintMyGraph()
{cout << "图的邻接矩阵存储为：" << endl;for (int i = 0; i < V; i++){for (int j = 0; j < V; j++){cout << Graph[i][j] << " ";}cout << endl;}
}//typedef struct DjNode
//{
//	int _index;
//	int _length;
//	int _prev;
//}Node;//Node BuyNode(int index, int length)
//{
//	Node* newnode = (Node*)malloc(sizeof(Node));
//	newnode->_index = index;
//	newnode->_length = length;
//	newnode->_prev = 0;
//	return newnode;
//}//typedef bool (*PCOM)(const Node& left, const Node& right);
//bool Compare(const Node left, const Node right)
//{
//	return left._length > right._length;
//}class Node
{
public:Node(int index, int length, int prev): _index(index), _length(length), _prev(prev){}Node(const Node& d){_index = d._index;_length = d._length;_prev = d._prev;}Node& operator=(const Node& node){if (this != &node){_index = node._index;_length = node._length;_prev = node._prev;}return *this;}bool operator>(const Node& d)const{return _length > d._length;}bool operator<(const Node& d)const{return _length < d._length;}int _index;int _length;int _prev;
};class Com
{
public:bool operator()(const Node&left, const Node&right)const{return left._length > right._length;}
};void Print_output(int start, vector<Node> node)
{cout << "由" << start << "到其余各顶点距离分别为" << endl;for (int i = 0; i < V; i++){if (i == start)continue;elsecout << start << "->" << i << ": " << node[i]._length << endl;}
}void Dijkstra_Algorithm()
{// 1、初始化输出数组D、P//vector<int> D(V, MAX);	// 初始化最短长度数组D//vector<int> P(V, 0);	// 初始化前驱结点数组Pvector<Node> node(V, Node(0,0,0));for (int i = 0; i < V; i++){//node[i] = BuyNode(i, MAX); // 结点初始化node[i]._index = i;node[i]._length = MAX;node[i]._prev = 0;}// 2、初始化顶点D[S]cout << "请输入起点" << endl;cin >> S;node[S]._length = 0;// 3、创建优先队列，起点元素入队列priority_queue<Node, vector<Node>, greater<Node>> q; q.push(node[S]);while (!q.empty()){Node cur = q.top();q.pop(); // 取出堆顶元素并进行保存vector<int> pre_next;int Index = cur._index;for (int i = 0; i < V; i++) // 将所有可以一步到达当前结点的元素下标全部保存到pre_next中{if (Graph[Index][i] > 0 && Graph[Index][i] != MAX)pre_next.push_back(i);}while (!pre_next.empty())	// 对于每一个可以到达cur的结点{int back = pre_next.back();	//访问一个取出一个pre_next.pop_back();// 新距离就为 从源点到back距离  加上  back到cur的距离int newlength = node[Index]._length + Graph[Index][back];// 如果新距离小于cur之前的最小距离，就将cur重新赋值，并入队列if (newlength < node[back]._length){node[back]._length = newlength;node[back]._prev = Index;q.push(node[back]);}}}cout << endl;Print_output(S, node);
}void _Dijkstra_Algorithm()
{cout << "Dijkstra_Algorithm :" << endl;int choice;while (1){cout << "请输入：" << "[1]开始" << "[0]结束" << endl;cin >> choice;switch (choice){case 1:Dijkstra_Algorithm();break;case 0:exit(0);break;}}
}int main()
{int choice;while (1){cout << "*******************************************" << endl;cout << "***************请输入请求：****************" << endl;cout << "***************[1]初始化数据***************" << endl;cout << "***************[2]迪杰斯特拉算法***********" << endl;cout << "***************[0]退出*********************" << endl;cout << "*******************************************" << endl;cin >> choice;switch (choice){case 1:CreatMyGraph();break;case 2:_Dijkstra_Algorithm();break;case 0:exit(0);break;default:cout << "输入错误,请重新输入" << endl;break;}}return 0;
}