煤气管道设计.cpp

一个最短路径算法

/*N(N>10)个居民区之间需要铺设煤气管道。假设任意两个居民区之间都可以
铺设煤气管道，但代价不同。事先将任意两个居民区之间铺设煤气管道的代
价存入磁盘文件中。设计一个最佳方案使得这N个居民区之间铺设煤气管道所需
代价最少，并希望以图形方式在屏幕上输出结果。*/




#include<iostream.h>
#include<stdlib.h>
#include<iomanip.h>
#include<stdio.h>
#include<fstream.h>

typedef char ElemType;
const int QueueMaxSize=30;

#include"queue.h"
const int MaxVertexNum=100;
const int MaxEdgeNum=100;
const int MaxValue=1000;
typedef char VertexType;
typedef VertexType vexlist[MaxVertexNum];
typedef int adjmatrix[MaxVertexNum][MaxVertexNum];
bool visited[MaxVertexNum];

struct edge
{
	int fromvex;
	int endvex;
	int weight;
};
typedef edge edgeset[MaxEdgeNum];

void Create(vexlist GV,adjmatrix GA,int n,int e)
{
	int i,j;
	/*cout<<"输入"<<n<<"个顶点"<<endl;
	for(i=0;i<n;i++)
		cin>>GV[i];*/
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		{
			if(i==j)
				GA[i][j]=0;
			else
				GA[i][j]=MaxValue;
		}
	/*	cout<<"输入"<<e<<"条边"<<endl;
		for(k=0;k<e;k++)
		{
			cin>>i>>j>>w;
			GA[i][j]=GA[j][i]=w;
		}*/
	/*	for(i=0;i<=n;i++)
		{
			for(j=0;j<=n;j++)
			{
				if(i==j)*/
	int v,m;
	FILE *fp;
	fp=fopen("data.txt","r");
	fscanf(fp,"%d %d",&v,&m);
	//cout<<v<<' '<<e<<endl;
	for(int x=1;x<=m;x++)
	{
		int i,j,k;
		fscanf(fp,"%d %d %d",&i,&j,&k);
		GA[i][j]=GA[j][i]=k;
	}
					
}

void Prim(adjmatrix GA,edgeset CT,int n)
{
	int min,t,m,w;
	for(int i=0;i<n-1;i++)
	{
		CT[i].fromvex=0;
		CT[i].endvex=i+1;
		CT[i].weight=GA[0][i+1];
	}
	for(int k=1;k<n;k++)
	{
		min=MaxValue;
		m=k-1;
		for(int j=k-1;j<n-1;j++)
			if(CT[j].weight<min)
			{
				min=CT[j].weight;
				m=j;
			}
			edge temp=CT[k-1];
			CT[k-1]=CT[m];
			CT[m]=temp;
			j=CT[k-1].endvex;
			for(i=k;i<n-1;i++)
			{
				t=CT[i].endvex;
				w=GA[j][t];
				if(w<CT[i].weight)
				{
					CT[i].weight=w;
					CT[i].fromvex=j;
				}
			}
	}
}


void main()
{
	int d;
	for(d=1;d<=20;d++)
		cout<<' ';
	cout<<"管道铺设施工的最佳方案选择"<<endl;//<<endl;
	//cout<<"数科院"；
    //int d;
	//for(d=1;d<=6;d++)
		//cout<<' ';
	cout<<"数科院"<<' '<<"06010824"<<' '<<"李方力"<<endl;//<<endl;
	cout<<"请注意:本程序管道起点必须为0!"<<endl;//<<endl;
	vexlist GV;
	adjmatrix GA;
	edgeset CT;
	int v,e;
	FILE *fp;
	fp=fopen("data.txt","r");
	fscanf(fp,"%d %d",&v,&e);
	cout<<"点数:"<<v<<setw(6)<<' '<<"边数:"<<e<<endl;//<<endl;
	Create(GV,GA,v,e);
//	cout<<"输出各边的起点，终点以及权值:"<<endl;
	for(int x=1;x<=e;x++)
	{
		int i,j,k;
		fscanf(fp,"%d %d %d",&i,&j,&k);
		if(i!=0&&x==1)
		{
			cout<<"请看清本程序要求!"<<endl;
			exit(1);
		}
        if(x==1)
			cout<<"输出:"<<' '<<"起点"<<setw(6)<<"终点"<<setw(6)<<"权值:"<<endl;
	//	cout<<i<<' '<<' '<<' '<<j<<' '<<' '<<' '<<k<<endl;
		cout<<' '<<' '<<' '<<' '<<' '<<' '<<' '<<i<<setw(6)<<j<<setw(6)<<k<<endl;
	}
	//cout<<endl;
	Prim(GA,CT,v);
	cout<<"输出最短路径:"<<endl;
	int sum=0;
	FILE *f;
	f=fopen("data1.txt","w");
	fprintf(f,"输出最短路径存档:\n");
	for(int m=0;m<v-1;m++)
	{
	//	FILE *f;
	//	f=fopen("data1.txt","w+t");
		if(m==5)
			cout<<endl;
        fprintf(f,"%d->%d\n",CT[m].fromvex,CT[m].endvex);
		cout<<CT[m].fromvex<<"->"<<CT[m].endvex<<setw(4);
		
		sum=sum+GA[CT[m].fromvex][CT[m].endvex];
	}
	cout<<endl;
    fprintf(f,"输出最短路径代价存档:%d\n",sum);
	fclose(f);
	cout<<"最佳方案所需代价:"<<sum<<endl;
}