乡卫生所选址（最短路径问题）

设计内容： 某乡有 A，B，C，D，E 5 个村庄，如下图所示，图中边上的权值表示两村之间的距离。现要在 5 个村庄中选某个村庄建立卫生所。其选址应使得距离卫生所最远的村庄到卫生所最近。

设计要求： (1) 给出各村庄之间最短距离的矩阵 A； (2) 卫生所应设在哪个村庄？输出各村庄到卫生所的路径和路径长度。

 

#include <iostream>
#define N 100
using namespace std;
void main()
{
	char v[N] = { 0 };//存放顶点字母
	int n;
	int e[N][N] = { 0 };//存放两地之间的距离
	cout << "输入顶点个数" << endl;
	cin >> n;
	cout << "输入顶点字母" << endl;
	for (int i = 0; i < n; i++)
		cin >> v[i];
	cout << "输入两地之间的距离" << endl;
 
	//输入邻接矩阵
	for (i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
		{
			cout << "输入" << v[i] << "到" << v[j] << "之间的距离（没有直接路径请输入‘100’）" << endl;
			cin >> e[i][j];
			e[j][i] = e[i][j];
		}
	for ( i = 0; i < n; i++)
		for (int j = 0; j < n; j++)//让对角线元素都为0
		{
			if (i == j)
				e[i][j] = 0;
		}
	cout << endl;
	//求出最短路径矩阵
	cout << "最短距离矩阵为：" << endl;
	int p=0;
	while(p!=n)
	{
		p++;
	for ( i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			for (int k = 0; k < n; k++)
			{
 
				if (e[i][j] > e[i][k] + e[k][j])
 
				{
					e[i][j] = e[i][k] + e[k][j];
 
				}
 
				if (i == j)
					e[i][j] = 0;
			}
		}
	}
	}
	for ( i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout<<" "<< e[i][j] << " ";
		}
		cout << endl;
		cout << endl;
	}


	//输出卫生所所在村庄
	char M;
	int min = N;
	//int m[sizeof(e[n][n])]={N};
	int y;
	//int sum=0;
	for ( i = 0; i < n; i++)
	{
		int sum = 0;
		for (int j = 0; j < n; j++)
		{
			sum += e[i][j];
		}
 
		if (min > sum)
		{
 
			min = sum;
			M = v[i];
			y = i;
		}
 
	}
	cout << "卫生所应建在" << M << "地" << endl;
	//输出卫生所到各点的距离
 
	for ( i = 0; i < n; i++)
		if (M != v[i])
		{
			cout << M << "地距" << v[i] << "地的距离为：";
			cout << e[i][y] << endl;
		}
 
	//输出最短路径
	int s=0;
	for(i=0;i<n;i++)
	{
	s+=e[i][y];
	}
	cout<<endl;
	cout << "最短路径长度为：" << min << endl;
}

运行结果：

 用VC++6.0编译的，要是用别的，可能要稍微改一下！！！