数据结构实验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();
}