t_floyd.cpp

用从c＋＋写的floyd最短路径算法

// T_floyd.cpp: implementation of the T_floyd class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "path.h"
#include "T_floyd.h"
#include <math.h>


#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif




//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

T_floyd::T_floyd()
:NAN(88888888)  ,m_N(0)    //为无穷大赋值
{
 

}

T_floyd::~T_floyd()
{

}

double T_floyd::add(double x, double y)     //定义两个数相加；含有无穷大的加法
{
    double z;
	if(fabs(x)>=NAN||fabs(y)>=NAN)
	{
		return NAN;
	}
	else
	{
		z=x+y;
		return z;
	}
}

void T_floyd::floyd()  //得出m_pred矩阵
{
	for(int k=0;k<m_N;k++)
	{
		for(int i=0;i<m_N;i++)
		{
			for(int j=0;j<m_N;j++)
			{
				if(add(m_dis[i*m_N+k],m_dis[k*m_N+j])<m_dis[i*m_N+j])
				{
					m_dis[i*m_N+j]=add(m_dis[i*m_N+k],m_dis[k*m_N+j]);
					m_pred[i*m_N+j]=m_pred[k*m_N+j];
				}
			}
			j=0;
		}
		i=0;
	}
}

void   T_floyd::initPred()//初始化m_pred
{
     m_pred.reserve(m_N*m_N);

	for(int i=0;i<m_N;++i)
	{
		for(int j=0;j<m_N;j++)
		{
			m_pred[i*m_N+j]=i;
		
		}
		j=0;
	}
}

void T_floyd::print(int i,int j)   //第i个顶点与第j个顶点的                                
{                                  //最短路径存储在m_result中
  for(int k=0;k<m_N;k++)
	{
		if(m_pred[i*m_N+j]==k)
		{
			if(i==k)
				return;
			m_result.push_back(k);
			print(i,k);
		}
	}
}

void T_floyd::out(CDC* pDC,int i,int j)//第i个顶点与第j个顶点的    
{                                      //最短路径输出到pDC设备上

	m_result.empty();
	print(i,j);

	CString s1;
	CString s2;
	CString s3;
	CString s;
	s1.Format("%d,",i);
    s2.Format("%d,",j);
    s="从顶点"+s1+"到顶点"+s2+"最短路径为：";
	pDC->TextOut(0,20,s);
   pDC->TextOut(0,40,s1);
   int k=2;
   int t;
	for( t=m_result.size()-1;t>=0; t--)
	{
		s3.Format("%d,",m_result.at(t));

		pDC->TextOut(10*k,40,s3);
		k++;

	}
	k++;
	pDC->TextOut(10*k,40,s2);


}

void T_floyd::initDis(double dis[])//初始化m_Dis
{
 for(int i=0;i<m_N*m_N;i++)
 {
	 m_dis.push_back(dis[i]);
 }
}