This is the third day of my participation in the August More text Challenge. For details, see: August More Text Challenge

## Dijkstra algorithm and Freud algorithm are used

Find the shortest path and the shortest distance between the two scenic spots

• Undirected graph: By inputting the number of nodes and the number of lines, input the weight of each line to calculate the shortest (optimal) line.
• Ps: Compile and run using Qt
``````/*
* 基于最短路径的景点规划
* 简介：分别采用迪杰斯特拉算法和弗洛伊德算法，求出两个景点间的最短路径和最短距离。
* 作者：181203616-宋明桥-GodOuO
* 修改履历：
*  21年8月，创建文件
*/

#include<iostream>
#include<string>
using namespace std;

class Dis {
public:
Dis() {
visit = false;
value = 0;
path = "";
}
public:
string path;
int value;
bool visit;
};
class Graph_fld {
public:
Graph_fld(int vexnum, int edge);
~Graph_fld();
bool check_edge_value(int start, int end, int weight);
void createGraph(int);
void Floyd();
void print_path(int);
void print();
private:
int vexnum;
int edge;
int **arc;
int ** dis;
int ** path;
};
class Graph_dis {
public:
Graph_dis(int vexnum, int edge);
~Graph_dis();
bool check_edge_value(int start, int end, int weight);
void createGraph();
void print();
void Dijkstra(int begin);
void print_path(int);
private:
int vexnum;   //图的顶点个数
int edge;     //图的边数
int **arc;   //邻接矩阵
Dis * dis;   //记录各个顶点最短路径的信息
};

Graph_fld::Graph_fld(int vexnum, int edge) {
this->vexnum = vexnum;
this->edge = edge;
arc = new int*[this->vexnum];
dis = new int*[this->vexnum];
path = new int*[this->vexnum];
for (int i = 0; i < this->vexnum; i++) {
arc[i] = new int[this->vexnum];
dis[i] = new int[this->vexnum];
path[i] = new int[this->vexnum];
for (int k = 0; k < this->vexnum; k++) {
arc[i][k] = INT_MAX;
}}}
Graph_dis::Graph_dis(int vexnum, int edge) {//初始化顶点数和边数
this->vexnum = vexnum;
this->edge = edge;
arc = new int*[this->vexnum];
dis = new Dis[this->vexnum];
for (int i = 0; i < this->vexnum; i++) {
arc[i] = new int[this->vexnum];
for (int k = 0; k < this->vexnum; k++) {
arc[i][k] = INT_MAX;
}}}

Graph_fld::~Graph_fld() {
for (int i = 0; i < this->vexnum; i++) {
delete this->arc[i];
delete this->dis[i];
delete this->path[i];
}
delete dis;
delete arc;
delete path;
}
Graph_dis::~Graph_dis() {
delete[] dis;
for (int i = 0; i < this->vexnum; i++) {
delete this->arc[i];
}
delete arc;
}

bool Graph_fld::check_edge_value(int start, int end, int weight) {
if (start<1 || end<1 || start>vexnum || end>vexnum || weight < 0) {
return false;
}
return true;
}
bool Graph_dis::check_edge_value(int start, int end, int weight) {
if (start<1 || end<1 || start>vexnum || end>vexnum || weight < 0) {
return false;
}
return true;
}

void Graph_fld::createGraph(int kind) {
cout << "请输入每条边的起点和终点（顶点编号从1开始）以及其权重：('1 2 8'-“V1到V2距离为8”)" << endl;
int start;
int end;
int weight;
int count = 0;
while (count != this->edge) {
cin>>start>>end>>weight;
while (!this->check_edge_value(start,end,weight)) {
cout<<"输入的边的信息不合法，请重新输入"<<endl;
cin>>start>>end>>weight;
}
arc[start - 1][end - 1] = weight;
if(2==kind)
arc[end-1][start-1] = weight;
++count;}}
void Graph_dis::createGraph() {
cout << "请输入每条边的起点和终点（顶点编号从1开始）以及其权重" << endl;
int start;
int end;
int weight;
int count = 0;
while (count != this->edge) {
cin >> start >> end >> weight;
while (!this->check_edge_value(start, end, weight)) {
cout << "输入的边的信息不合法，请重新输入" << endl;
cin >> start >> end >> weight;
}
arc[start - 1][end - 1] = weight;
arc[end - 1][start - 1] = weight;
++count;
}}

void Graph_fld::Floyd() {
int i=0,j=0;
for (i= 0; i< this->vexnum; i++) {
for (j=0; j< this->vexnum; j++) {
this->dis[i][j] = this->arc[i][j];
this->path[i][j] = j;}}
int n=0;
for (int m = 0;m<this->vexnum;m++) {
for (i = 0;i < this->vexnum; i++) {
for (j = 0; j< this->vexnum; j++) {
n=(dis[i][m]==INT_MAX||dis[m][j] == INT_MAX)?INT_MAX:(dis[i][m] + dis[m][j]);
if (this->dis[i][j]>n) {
this->dis[i][j]=n;
this->path[i][j]=this->path[i][m];
}}}}}
void Graph_dis::Dijkstra(int begin){
int i;
for (i = 0; i < this->vexnum; i++) {
dis[i].path = "v" + to_string(static_cast<long long>(begin)) + "-->v" + to_string(static_cast<long long>(i + 1));
dis[i].value = arc[begin - 1][i];
}
dis[begin - 1].value = 0;
dis[begin - 1].visit = true;
int count = 1;
while (count != this->vexnum) {
int temp=0;
int min = INT_MAX;
for (i = 0; i < this->vexnum; i++) {
if (!dis[i].visit && dis[i].value<min) {
min = dis[i].value;
temp = i;
}}
dis[temp].visit = true;
++count;
for (i = 0; i < this->vexnum; i++) {
if (!dis[i].visit && arc[temp][i]!=INT_MAX && (dis[temp].value + arc[temp][i]) < dis[i].value) {
dis[i].value = dis[temp].value + arc[temp][i];
dis[i].path = dis[temp].path + "-->v" + to_string(static_cast<long long>(i + 1));
}}}}

void Graph_fld::print() {
cout << "图的邻接矩阵为：" << endl;
int i = 0; //i代表打印行
int j = 0; //j代表打印列
while (i != this->vexnum) {
j = 0;
while (j!= this->vexnum) {
if (arc[i][j] == INT_MAX)
cout << "∞" << " ";
else
cout << arc[i][j] << " ";
++j;
}
cout << endl;
++i;
}}
void Graph_dis::print() {
cout << "图的邻接矩阵为：" << endl;
int i= 0; //打印行
int j= 0; //打印列
while (i != this->vexnum) {
j= 0;
while (j!= this->vexnum) {
if (arc[i][j] == INT_MAX)
cout << "∞" << " ";
else
cout << arc[i][j] << " ";
++j;}
cout << endl;
++i;
}}

void Graph_fld::print_path(int begin) {
cout << "各个顶点对的最短路径：" << endl;
int i = 0;
int j = 0;
int m = 0;
for (i=begin-1;i<begin;i++) {
for (j= 0; j< this->vexnum;j++) {
if(0!=(to_string(static_cast<long long>(i+ 1)).compare(to_string(static_cast<long long>(j+ 1))))){
cout << "v" << to_string(static_cast<long long>(i+ 1)) << "---" << "v" << to_string(static_cast<long long>(j+ 1)) << "最短路径长度为： "
<< this->dis[i][j] << "\n\t\t\t最短路径为： " << "v" << to_string(static_cast<long long>(i+ 1));
m = path[i][j];
while (m!= j) {
cout << "-->" << "v" << to_string(static_cast<long long>(m + 1));
m= path[m][j];
}
cout << "-->" << "v" << to_string(static_cast<long long>(j + 1));

cout << endl;}
else{cout << "v" << to_string(static_cast<long long>(i+ 1)) << "---" << "v" << to_string(static_cast<long long>(j+ 1)) << "最短路径长度为： "
<<0 << "\n\t\t\t最短路径为： v" << to_string(static_cast<long long>(i+ 1)) << "-->v"<<to_string(static_cast<long long>(j+ 1))<<endl;}
}}}
void Graph_dis::print_path(int begin) {
string str;
str = "v" + to_string(static_cast<long long>(begin));
cout << "以"<<str<<"为起点的图的最短路径为：" << endl;
for (int i = 0; i != this->vexnum; i++) {
if(dis[i].value!=INT_MAX)
cout<<str<<"---v"<<i+1<<"最短路径长度为： "<< dis[i].value <<"\n\t\t\t最短路径为： "<<dis[i].path<<endl;
else {
cout << dis[i].path << "当前没有最短路径" << endl;
}}}

bool check(int Vexnum, int edge) {
if (Vexnum <= 0 || edge <= 0 || ((Vexnum*(Vexnum - 1)) / 2) < edge)
return false;
return true;}

int main() {
int vexnum=0; int edge=0; int sel=0; int s=0;
while(1){
cout<<"\n输入数字运行功能 \n 1.基于迪杰斯特拉算法最短路径计算 \n 2.基于和弗洛伊德算法最短路径计算 \n 3.Quit \n"<<endl;
cin>>s;

if(1==s){//迪杰斯特拉算法
cout << "\n输入图的顶点个数和边的条数：('3 2'-“3顶点，2条线”)" << endl;
cin >> vexnum >> edge;
while (!check(vexnum, edge)) {
cout << "输入的数值不合法，请重新输入" << endl;
cin >> vexnum >> edge;}
Graph_dis graph(vexnum, edge);
graph.createGraph();
graph.print();

while(1){
s=0;
cout<< "\n 输入数字运行功能 \n 1.运行计算 \n 2.Quit \n" <<endl;
cin>>s;
if(1==s){
cout<< "请输入初始点，输入后将遍历所有节点最短距离：('1'-V1点出发到各点最短路径)" <<endl;
cin>>sel;
graph.Dijkstra(sel);
graph.print_path(sel);}
else if(2==s){
break;
}else{
cout<<"请输入正确值！"<<endl;
}}}

else if(2==s){//弗洛伊德算法
cout << "输入图的顶点个数和边的条数：('3 2'-“3顶点，2条线”)" << endl;
cin >> vexnum >> edge;
while (!check(vexnum, edge)) {
cout << "输入的数值不正确，请重新输入" << endl;
cin >> vexnum >> edge;}
Graph_fld graph(vexnum, edge);
graph.createGraph(2);
graph.print();

while(1){
s=0;
cout<< "\n 输入数字运行功能 \n 1.运行计算 \n 2.Quit \n" <<endl;
cin>>s;
if(1==s){
cout<< "请输入初始点，输入后将遍历所有节点最短距离：('1'-V1点出发到各点最短路径)" <<endl;
cin>>sel;
graph.Floyd();
graph.print_path(sel);}else if(2==s){
break;
}else{
cout<<"请输入正确值！"<<endl;
}}}

else if(3==s){//Quit
cout<<"BYE!"<<endl;
system("pause");
return 0;
}else{
cout<<"请输入正确数字！"<<endl;
}}}
Copy the code``````