Catalog
数据结构实验7之迪杰斯特拉最短路径

以山东大学威海的部分建筑物为例来实现迪杰斯特拉算法

#include <iostream>
#include <map>
#include <string>

using namespace std;
map<string, int> couple;
int e[20][20], dis[20], book[20], min, n, u, v, m, t1, t2, t3, infinity = 9999999;
void map_init() {
couple["泰园餐厅"] = 1;
couple["6号楼"] = 2;
couple["5号楼"] = 3;
couple["体育馆"] = 4;
couple["田径场"] = 5;
couple["馨园餐厅"] = 6;
couple["荟园餐厅"] = 7;
couple["法学院"] = 8;
couple["雀园餐厅"] = 9;
couple["电子楼"] = 10;
couple["图书馆"] = 11;
couple["网络楼"] = 12;
couple["数学院"] = 13;
couple["教师公寓"] = 14;
couple["机电院"] = 15;
}
void create_matrix() {

for (int i = 1; i <= 15; i++)
for (int j = 1; j <= 15; j++)
if (i == j) e[i][j] = 0;
else e[i][j] = infinity;
}

void input_matrix(string a,string b) {
e[1][2] = 50;e[2][1] = 50;
e[1][6] = 50;e[6][1] = 50;
e[2][3] = 20;e[3][2] = 20;
e[3][4] = 289;e[4][3] = 289;
e[4][5] = 150;e[5][4] = 150;
e[7][6] = 50; e[6][7] = 50;
e[7][8] = 150; e[8][7] = 150;
e[8][9] = 200; e[9][8] = 200;
e[9][10] = 200; e[10][9] = 200;
e[10][5] = 100; e[5][10] = 100;
e[10][12] = 100; e[12][10] = 100;
e[10][11] = 160; e[11][10] = 160;
e[11][12] = 150; e[12][11] = 150;
e[11][13] = 250; e[13][11] = 250;
e[12][13] = 170; e[13][12] = 170;
e[8][13] = 300; e[13][8] = 300;
e[8][11] = 190; e[11][8] = 190;
e[12][14] = 400; e[14][12] = 400;
e[13][15] = 500; e[15][13] = 500;
e[14][15] = 1000; e[15][14] = 1000;

if (couple[a] > couple[b]) {
int t;
t = couple[a];
couple[a] = couple[b];
couple[b] = t;
}
for (int i = 1; i <= 15; i++)
dis[i] = e[couple[a]][i];

for (int i = 1; i <= 15; i++)
book[i] = 0;
book[couple[a]] = 1;
}

void dijkstra() {
for (int i = 1; i <= 14; i++) {

min = infinity;
for (int j = 1; j <= 15; j++)
{
if (book[j] == 0 && dis[j] < min) {
min = dis[j];
u = j;
}
}
book[u] = 1;
for (v = 1; v <= 15; v++) {
if (e[u][v] < infinity) {
if (dis[v] > dis[u] + e[u][v])
dis[v] = dis[u] + e[u][v];
}
}
}

}
void print() {
int i = 1;
cout << "以图片的实例为标准,以泰园餐厅为起点" << endl << endl;
cout << "到达6号楼的最短路径为" << dis[i+1] << endl << endl;
cout << "到达5号楼的最短路径为" << dis[i+2] << endl << endl;
cout << "到达体育馆的最短路径为" << dis[i+3] << endl << endl;
cout << "到达田径场的最短路径为" << dis[i+4] << endl << endl;
cout << "到达馨园餐厅的最短路径为" << dis[i+5] << endl << endl;
cout << "到达荟园餐厅的最短路径为" << dis[i+6] << endl << endl;
cout << "到达法学院的最短路径为" << dis[i+7] << endl << endl;
cout << "到达雀园餐厅的最短路径为" << dis[i+8] << endl << endl;
cout << "到达电子楼的最短路径为" << dis[i+9] << endl << endl;
cout << "到达图书馆的最短路径为" << dis[i+10] << endl << endl;
cout << "到达网络楼的最短路径为" << dis[i+11] << endl << endl;
cout << "到达数学院的最短路径为" << dis[i+12] << endl << endl;
cout << "到达教师公寓的最短路径为" << dis[i+13] << endl << endl;
cout << "到达机电院的最短路径为" << dis[i+14] << endl << endl;
}

int main() {
string a = "泰园餐厅";
string b = "机电院";
map_init();
create_matrix();
input_matrix(a,b);
dijkstra();
print();
}

Author: superzhaoyang
Link: http://yoursite.com/2019/12/02/数据结构实验七之迪杰斯特拉最短路径/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
  • 支付宝
��