算法实训课程-贵师大地图智能导航-基于最短路径算法

本文主要是介绍算法实训课程-贵师大地图智能导航-基于最短路径算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

PDF：
1. 演示：
2. 下载：链接：https://pan.baidu.com/s/1rQWonClneqv-Wh7IZyJ0Vg
  提取码：6nud

C++算法：

#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
#include <stack>using namespace std;
#define inf 999999
#define nmax 110
int n, m, edge[nmax][nmax], path[nmax][nmax], value[nmax][nmax];struct vertex
{// 点编号1~nint id;// 该点名字, 例如（贵师大等等）string name;
} V[nmax];ofstream fout;
ifstream fin;
// 初始化边
void init();// 全局变量初始化
void dataInit();// 手动输出边
void input();
// 保存边
void save();
// 计算最短路径
void minPath();
// 打印最短路径值
void print_min_value();
// 打印路径
void print_path(int i, int j);
//
void get();//增加一个点
void addVertex();// 查看所有位置信息
void showAllVerter();int main()
{dataInit();init();// input();// get();// addVertex();// minPath();showAllVerter();get();// save();return 0;
}void init()
{fin.open("./edge", ios::in);fin >> n;for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)fin >> edge[i][j];fin.close();// 加载位置信息fin.open("./vecter", ios::in);for (int i = 1; i <= n; ++i){fin >> V[i].id >> V[i].name;}fin.close();// 加载计算后的数据fin.open("./value", ios::in);for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)fin >> value[i][j];fin.close();// 加载路径fin.open("./path", ios::in);for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)fin >> path[i][j];fin.close();
}void get()
{int i, j;cout << "please enter the start and end (0 0 end the enter!):" << endl;while (cin >> i >> j && i && j){cout << i << " -> " << j << " : ";cout << value[i][j] << endl;cout << "path"<< " : ";print_path(i, j);}
}void save()
{// 保存位置信息fout.open("./vecter", ios::out);for (int i = 1; i <= n; ++i){fout << V[i].id << " " << V[i].name << endl;}fout.close();fout.open("./edge", ios::out);// 点的总数fout << n << endl;// 保存边for (int i = 1; i <= n; ++i){for (int j = 1; j <= n; ++j)fout << edge[i][j] << " ";fout << endl;}fout.close();fout.open("./value", ios::out);// 保存以计算后的数据for (int i = 1; i <= n; ++i){for (int j = 1; j <= n; ++j)fout << value[i][j] << " ";fout << endl;}fout.close();// 保存路径fout.open("./path", ios::out);for (int i = 1; i <= n; ++i){for (int j = 1; j <= n; ++j)fout << path[i][j] << " ";fout << endl;}fout.close();
}void input()
{memset(edge, inf, sizeof(edge));memset(value, inf, sizeof(value));memset(path, -1, sizeof(path));string name;int i, j;cout << "输入该位置名称(end结束输入!)" << endl;while (cin >> name && name != "end"){cout << "该位置的编号为: " << ++n << endl;V[n].id = n;V[n].name = name;cout << "请输入该位置与其他位置之间的距离，格式：s e 100(0 0结束)" << endl;while (cin >> i >> j && (i && j)){cin >> edge[i][j];edge[j][i] = edge[i][j];}}minPath();save();
}void minPath()
{// 重新计算valuefor (int i = 1; i <= n; ++i){value[i][i] = edge[i][i] = 0;for (int j = 1; j <= n; ++j)value[i][j] = edge[i][j];}memset(path, -1, sizeof(path));for (int k = 1; k <= n; k++){for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){if (value[k][j] < inf && value[i][k] < inf && value[i][j] > value[i][k] + value[k][j]){value[i][j] = value[i][k] + value[k][j];path[i][j] = k;}}}}
}// 打印路径
void print_path(int i, int j)
{int flag = 0;if (i > j){flag = 1;swap(i, j);}stack<int> Q;while (true){if (i == j){cout << V[i].name << " --> " << V[i].name << endl;break;}// i->j　中间无位置，且可直达else if (path[i][j] == -1 && edge[i][i] != inf){Q.push(j);Q.push(i);break;}// i->j　不可到达else if (path[i][j] == -1 && edge[i][i] == inf){cout << V[i].name << " --> " << V[j].name << "　不可到达" << endl;}// i->j之间还有位置else if (path[i][j] != -1){Q.push(j);j = path[i][j];}}// stack去倒置if (flag){stack<int> temp;while (!Q.empty()){temp.push(Q.top());Q.pop();}Q.swap(temp);}// 打印位置路径while (!Q.empty()){int index = Q.top();Q.pop();cout << V[index].name;if (!Q.empty())cout << " -->> ";else{cout << endl;}}
}
//增加一个点
void addVertex()
{// todo 有bugcout << "请输入该位置的名称(end结束)：";string name;cin >> name;n++;V[n].id = n;V[n].name = name;for (int i = 1; i <= n; ++i){edge[i][n] = edge[n][i] = inf;}edge[n][n] = 0;cout << "该位置的编号为: " << n << endl;cout << "请输入该位置与其他位置之间的距离，格式：s e 100(0 0结束)" << endl;int i, j;while (cin >> i >> j && i && j){cin >> edge[i][j];edge[j][i] = edge[i][j];}cout << "请输入该位置的名称(end结束)：";minPath();save();
}void showAllVerter()
{for (int i = 1; i <= n; ++i){cout << V[i].id << " " << V[i].name << endl;}
}void dataInit()
{n = 0;m = 0;memset(edge, inf, sizeof(edge));memset(path, -1, sizeof(path));memset(value, inf, sizeof(value));
}

测试数据：

西北门
0 0
西门
2 1 197
0 0
一食堂
3 1 255
3 2 155
0 0
二食堂
4 3 320
0 0
行政楼
5 4 305
0 0
新校区法学院
6 5 229
0 0
17栋宿舍
7 6 150
0 0
研究生学院
8 3 247
0 0
文学院
9 8 236
0 0
图书馆
10 9 187
0 0
end
机械与电机工程学院
11 10 245
0 0
三食堂
12 11 207
12 6 111
12 7 215
0 0
理科综合实验楼
13 11 75
13 10 260
0 0
物理与电子科学学院
14 13 320
14 10 185
0 0
外语学院
15 14 310
15 8 257
15 9 236
0 0