graph.cpp

多段图问题的解决

//
//		多段图的向前处理算法
//		蓝翔 
//		2003.11.29
////////////////////////////////////////////////

#include "StdAfx.h"

FGrAph::FGrAph()
{
	cout<<"出错!"<<endl;
}

FGrAph::FGrAph(int n)
{
	this->m_n = n;

	//this->m_dataArray = new double[m_n*m_n];
	this->m_cost = new double[m_n];
	this->m_path = new int[m_n];

	double temp[144] = {//just for test
		0,9,7,3,2,0,0,0,0,0,0,0,
		0,0,0,0,0,4,2,1,0,0,0,0,
		0,0,0,0,0,2,7,0,0,0,0,0,
		0,0,0,0,0,0,0,11,0,0,0,0,
		0,0,0,0,0,0,11,8,0,0,0,0,
		0,0,0,0,0,0,0,0,6,5,0,0,
		0,0,0,0,0,0,0,0,4,3,0,0,
		0,0,0,0,0,0,0,0,0,5,6,0,
		0,0,0,0,0,0,0,0,0,0,0,4,
		0,0,0,0,0,0,0,0,0,0,0,2,
		0,0,0,0,0,0,0,0,0,0,0,5,
		};

	for(int j = 0;j < (m_n*m_n); j ++)//设置测试数组元素值
	{
		this->m_dataArray[j] = temp[j];
		//cout<<this->m_dataArray[j]<<"\t";//just for test
	}	

	for(int i = 0;i < m_n;i ++)
	{
		this->m_cost[i] = 0;
		this->m_path[i] = -1;
	}
	cout<<endl;
}

FGrAph::~FGrAph()
{
	//if(this->m_dataArray != NULL)
	//	delete[] this->m_dataArray;
	if(this->m_cost != NULL)
		delete[] this->m_cost;
	if(this->m_path != NULL)
		delete[] this->m_path;
}

void FGrAph::readData()
{
BEGIN:
	cout<<"1.使用测试数据"<<endl
		<<"2.处定义数据"<<endl
		<<"请选择:";
	char chose;
	chose = getch();
	if(chose == '1')
	{
		cout<<endl<<endl<<"测试数据使用的书本91面的图4.1"<<endl;
		return;
	}
	else if(chose != '2')
	{
		cout<<endl<<"请重新..."<<endl;
		goto BEGIN;
	}

	//读入新边成本值
	for(int i = 0;i < m_n;i ++)
	{
		for(int j = 0;j < m_n; j ++)
		{
			double in;
			cout<<"请设置边"<<i+1<<"->"<<j+1<<"的成本：";
			cin>>in;
			this->setCost(i,j,in);
		}
	}
}

void FGrAph::handle()
{
	int* d = new int[this->m_n];
	for(int i = 0;i < this->m_n;i++)
	{
		d[i] = -1;
	}

	for(i = m_n-2;i >= 0;i --)//计算m_cost数组
	{
		int r = 0;
		double temp = 9999;//设置为一个较大有数值
		for(int j = 0;j < this->m_n;j ++)//找出r，使得getCost(i,r)+m_cost(r)为最小
		{
			if(j!=i && this->getCost(i,j) != 0 
				&& temp > (this->getCost(i,j) + this->m_cost[j]))
			{
				temp = this->getCost(i,j) + this->m_cost[j];
				r = j;
				//cout<<r<<endl;//just for test
			}
		}

		this->m_cost[i] = this->m_cost[r] + this->getCost(i,r);
		d[i] = r;
		//cout<<"min: "<<r+1<<"\tcost: "<<this->m_cost[i]<<","<<this->m_cost[r]<<endl;
	}

	this->m_path[0] = 0;

	int j = 1;
	while(d[this->m_path[j-1]] != -1)
	{
		this->m_path[j] = d[this->m_path[j-1]];//递推求出前一结点指向的下一结点
		j++;
	}

	delete[] d;
}

void FGrAph::printResult()
{
	cout<<"最小成本路径:"<<endl;
	int i = 0;
	while(this->m_path[i] != -1)
	{
		cout<<" -> "<<this->m_path[i] + 1;
		i++;
	}
	cout<<endl;
}

double FGrAph::getCost(int src,int det)
{
	return this->m_dataArray[(src * m_n) + det];
}

void FGrAph::setCost(int i,int j,double val)
{
	this->m_dataArray[(i * m_n) + j] = val;
}