xianluview.cpp

一个关于供求陪送的线路程序。里面用到了最短路径的知识

// xianluView.cpp : implementation of the CXianluView class
//

#include "stdafx.h"
#include "xianlu.h"
#include <windows.h>
#include "xianluDoc.h"
#include "xianluView.h"

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

/////////////////////////////////////////////////////////////////////////////
// CXianluView

IMPLEMENT_DYNCREATE(CXianluView, CFormView)

BEGIN_MESSAGE_MAP(CXianluView, CFormView)
	//{{AFX_MSG_MAP(CXianluView)
	ON_CBN_EDITCHANGE(IDC_Begin, OnEditchangeBegin)
	ON_CBN_EDITCHANGE(IDC_End, OnEditchangeEnd)
	ON_BN_CLICKED(IDC_BUTTON1, OnButton1)
	//}}AFX_MSG_MAP
	// Standard printing commands
	ON_COMMAND(ID_FILE_PRINT, CFormView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_DIRECT, CFormView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_PREVIEW, CFormView::OnFilePrintPreview)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CXianluView construction/destruction

CXianluView::CXianluView()
	: CFormView(CXianluView::IDD)
{
	//{{AFX_DATA_INIT(CXianluView)
	m_begin = _T("");
	m_end = _T("");
	m_string = _T("");
	m_Estring = _T("");
	m_lstring = _T("");
	m_string2 = _T("");
	//}}AFX_DATA_INIT
	// TODO: add construction code here
//	p_Begin->GetDlgItem(IDC_Begin);
//	p_End=(CComboBox*)GetDlgItem(IDC_End);
//	CXianluDoc* pDoc = GetDocument();
//	ASSERT_VALID(pDoc);
/*	i_begin=Get_i(m_begin);
	i_end=Get_i(m_end);
	if(i_begin>i_end)
		is_direction=FALSE;//从右向左
	else 
		is_direction=TRUE;
	if(is_direction)
	{
		pDoc->arcs[2][0]=1200;//从世界之窗到沃尔玛
		pDoc->arcs[2][3]=1000;//从世界之窗到南江百华
		pDoc->arcs[1][0]=500;//从华侨城到沃尔玛
		pDoc->arcs[2][0]=1200;//从世界之窗到沃尔玛
		pDoc->arcs[3][0]=1600;//从南江百华到沃尔玛
		pDoc->arcs[3][2]=1000;//从南江百华到世界之窗
		pDoc->arcs[4][1]=4200;//从华为通讯到华侨城
		pDoc->arcs[4][3]=2000;//从华为通讯到南江百华
		pDoc->arcs[5][3]=3000;//从中兴通讯到南江百华
		pDoc->arcs[5][4]=2700;//从中兴通讯到华为通讯
		pDoc->arcs[6][3]=2700;//从金长城公司到南江百华
		pDoc->arcs[6][4]=2900;//从金长城公司到华为通讯
		pDoc->arcs[6][5]=3300;//从金长城公司到中兴通讯
		pDoc->arcs[7][5]=1600;//从大学园到中兴通讯
		pDoc->arcs[7][6]=900;//从大学园到金长城公司
		pDoc->arcs[8][5]=2600;//从清华深圳研究生院到中兴通讯
		pDoc->arcs[8][7]=1300;//从清华深圳研究生院到大学园
		pDoc->arcs[9][7]=800;//从高新超市到大学园
		pDoc->arcs[9][8]=1000;//从高新超市到清华深圳研究生院
		pDoc->arcs[10][6]=2400;//从兰羽公司到金长城公司
		pDoc->arcs[10][9]=1100;//从兰羽公司到高新超市
		pDoc->arcs[11][4]=3300;//从华润超市到华为通讯
		pDoc->arcs[11][6]=2400;//从华润超市到金长城公司
		pDoc->arcs[11][7]=3100;//从华润超市到大学园
		pDoc->arcs[11][10]=1200;//从华润超市到兰羽公司

	}
	else
	{
		pDoc->arcs[0][1]=500;//从沃尔玛到华侨城
		pDoc->arcs[0][2]=1200;//从沃尔玛到世界之窗
		pDoc->arcs[0][3]=1600;//从沃尔玛到南江百华
		pDoc->arcs[1][4]=4200;//从华侨城到华为通讯
		pDoc->arcs[2][3]=1000;//从世界之窗到南江百华
		pDoc->arcs[3][4]=2000;//从南江百华到华为通讯
		pDoc->arcs[3][5]=3000;//从南江百华到中兴通讯
		pDoc->arcs[3][6]=2700;//从南江百华到金长城公司
		pDoc->arcs[4][5]=2700;//从华为通讯到中兴通讯
		pDoc->arcs[4][6]=2900;//从华为通讯到金长城公司
		pDoc->arcs[4][11]=3300;//从华为通讯到华润超市
		pDoc->arcs[5][6]=3300;//从中兴通讯到金长城公司
		pDoc->arcs[5][7]=1600;//从中兴通讯到大学园
		pDoc->arcs[5][8]=2600;//从中兴通讯到清华深圳研究生院
		pDoc->arcs[6][7]=900;//从金长城公司到大学园
		pDoc->arcs[6][10]=2400;//从金长城公司到兰羽公司
		pDoc->arcs[6][11]=2400;//从金长城公司到华润超市
		pDoc->arcs[7][8]=1300;//从大学园到清华深圳研究生院
		pDoc->arcs[7][9]=800;//从大学园到高新超市
		pDoc->arcs[7][11]=3100;//从大学园到华润超市
		pDoc->arcs[8][9]=1000;//从清华深圳研究生院到高新超市
		pDoc->arcs[9][10]=1100;//从高新超市到兰羽公司
		pDoc->arcs[10][11]=1200;//从兰羽公司到华润超市
	}
*/
}

CXianluView::~CXianluView()
{
}

void CXianluView::DoDataExchange(CDataExchange* pDX)
{
	CFormView::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CXianluView)
	DDX_CBString(pDX, IDC_Begin, m_begin);
	DDX_CBString(pDX, IDC_End, m_end);
	DDX_LBString(pDX, IDC_Lstring, m_lstring);
	DDX_LBString(pDX, IDC_Lstring2, m_string2);
	//}}AFX_DATA_MAP
}

BOOL CXianluView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs

	return CFormView::PreCreateWindow(cs);
}

void CXianluView::OnInitialUpdate()
{
	CFormView::OnInitialUpdate();
	ResizeParentToFit();

}

/////////////////////////////////////////////////////////////////////////////
// CXianluView printing

BOOL CXianluView::OnPreparePrinting(CPrintInfo* pInfo)
{
	// default preparation
	return DoPreparePrinting(pInfo);
}

void CXianluView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add extra initialization before printing
}

void CXianluView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add cleanup after printing
}

void CXianluView::OnPrint(CDC* pDC, CPrintInfo* /*pInfo*/)
{
	// TODO: add customized printing code here
}

/////////////////////////////////////////////////////////////////////////////
// CXianluView diagnostics

#ifdef _DEBUG
void CXianluView::AssertValid() const
{
	CFormView::AssertValid();
}

void CXianluView::Dump(CDumpContext& dc) const
{
	CFormView::Dump(dc);
}

CXianluDoc* CXianluView::GetDocument() // non-debug version is inline
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CXianluDoc)));
	return (CXianluDoc*)m_pDocument;
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CXianluView message handlers
int CXianluView::Get_i (CString string)
{
	int i;
	if(strcmp(string,"沃尔玛")==0)
		i=0;
	else if(strcmp(string,"华侨城")==0)
		i=1;
	else if(strcmp(string , "世界之窗")==0)
		i=2;
	else if(strcmp(string , "南江百华" )==0)
		i=3;
	else if(strcmp(string , "华为通讯")==0)
		i=4;
	else if(strcmp(string , "中兴通讯")==0)
		i=5;
	else if(strcmp(string ,  "金长城公司")==0)
		i=6;
	else if(strcmp(string , "大学园")==0)
		i=7;
	else if(strcmp(string ,  "清华深圳研究生院")==0)
		i=8;
	else if(strcmp(string ,  "高新超市")==0)
		i=9;
	else if(strcmp(string ,  "兰羽公司")==0)
		i=10;
	else if(strcmp(string ,  "华润超市")==0)
		i=11;
	return i;

}
void CXianluView::OnDraw(CDC* pDC) 
{
	// TODO: Add your specialized code here and/or call the base class
	
	CXianluDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	CBrush brushNew(RGB(0,0,255));
	CBrush *brushOld=pDC->SelectObject(&brushNew);
	for(int i=0;i<pDoc->vexnum;i++)
	{
    pDC->Ellipse(pDoc->c_Address[i].x-2,pDoc->c_Address[i].y-2,pDoc->c_Address[i].x+2,pDoc->c_Address[i].y+2);
	}
	//标记各地点名称
	pDC->TextOut (pDoc->c_Address[0].x+20,pDoc->c_Address[0].y+5,"沃尔玛");
	pDC->TextOut (pDoc->c_Address[1].x,pDoc->c_Address[1].y-25,"华侨城");
	pDC->TextOut (pDoc->c_Address[2].x+20,pDoc->c_Address[2].y-10,"世界之窗");
	pDC->TextOut (pDoc->c_Address[3].x-40,pDoc->c_Address[3].y+15,"南江百华");
	pDC->TextOut (pDoc->c_Address[4].x-30,pDoc->c_Address[4].y-20,"华为通讯");
	pDC->TextOut (pDoc->c_Address[5].x+20,pDoc->c_Address[5].y+20,"中兴通讯");
	pDC->TextOut (pDoc->c_Address[6].x-30,pDoc->c_Address[6].y+10,"金长城公司");
	pDC->TextOut (pDoc->c_Address[7].x,pDoc->c_Address[7].y-25,"大学园");
	pDC->TextOut (pDoc->c_Address[8].x-50,pDoc->c_Address[8].y+10,"清华深圳研究生院");
	pDC->TextOut (pDoc->c_Address[9].x-80,pDoc->c_Address[9].y-10,"高新超市");
	pDC->TextOut (pDoc->c_Address[10].x-80,pDoc->c_Address[10].y-10,"兰羽公司");
	pDC->TextOut (pDoc->c_Address[11].x-80,pDoc->c_Address[11].y-10,"华润超市");
	
		



	
}

void CXianluView::OnEditchangeBegin() 
{
	// TODO: Add your control notification handler code here
	

}

void CXianluView::OnEditchangeEnd() 
{
	// TODO: Add your control notification handler code here
	
}

void CXianluView::OnButton1() 
{
	// TODO: Add your control notification handler code here
	//InvalidateRect(FALSE);
	CXianluDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	CDC *pDC=GetDC();
	CComboBox *p_Begin=(CComboBox *)GetDlgItem(IDC_Begin);
	CComboBox *p_End=(CComboBox *)GetDlgItem(IDC_End);
	CListBox *p_text=(CListBox *)GetDlgItem(IDC_Lstring);
	CListBox *p_text2=(CListBox *)GetDlgItem(IDC_Lstring2);
	p_text->ResetContent ();
	p_text2->ResetContent ();
	int i_b,i_e;
	
		//取得起点信息
	i_b=p_Begin->GetCurSel ();
	p_Begin->GetLBText (i_b,m_begin);
	i_begin=Get_i(m_begin);
		//取得终点信息
	i_e=p_End->GetCurSel ();
	p_End->GetLBText (i_e,m_end);
    i_end=Get_i(m_end);

	CBrush NewBrush(RGB(255,0,0));
	CBrush *OldBrush=pDC->SelectObject (&NewBrush);
	pDC->Ellipse (pDoc->c_Address [i_begin].x-5,pDoc->c_Address [i_begin].y-5,pDoc->c_Address [i_begin].x+5,pDoc->c_Address [i_begin].y+5);
	pDC->Ellipse (pDoc->c_Address [i_end].x-5,pDoc->c_Address [i_end].y-5,pDoc->c_Address [i_end].x+5,pDoc->c_Address [i_end].y+5);
	for(int i=0;i<pDoc->vexnum;i++)
		for(int j=0;j<pDoc->vexnum;j++)
			pDoc->arcs[i][j]=MAX;	//给各路程赋予初值
	p_text->AddString ("从"+m_begin+"地到"+m_end);
	 
	if(pDoc->c_Address[i_begin].x >pDoc->c_Address[i_end].x )
		is_direction=0;//从右向左
	else 
		is_direction=1;
	if(is_direction==1)
	{
		pDoc->arcs[1][0]=5;//从华侨城到沃尔玛

		pDoc->arcs[2][0]=12;//从世界之窗到沃尔玛

		pDoc->arcs[3][0]=16;//从南江百华到沃尔玛
		pDoc->arcs[3][2]=10;//从南江百华到世界之窗

		pDoc->arcs[4][1]=42;//从华为通讯到华侨城
		pDoc->arcs[4][3]=20;//从华为通讯到南江百华

		pDoc->arcs[5][3]=30;//从中兴通讯到南江百华
		pDoc->arcs[5][4]=41;//从中兴通讯到华为通讯

		pDoc->arcs[6][3]=27;//从金长城公司到南江百华
		pDoc->arcs[6][4]=29;//从金长城公司到华为通讯
		pDoc->arcs[6][5]=33;//从金长城公司到中兴通讯

		pDoc->arcs[7][5]=16;//从大学园到中兴通讯
		pDoc->arcs[7][6]=9;//从大学园到金长城公司

		pDoc->arcs[8][5]=26;//从清华深圳研究生院到中兴通讯
		pDoc->arcs[8][7]=13;//从清华深圳研究生院到大学园

		pDoc->arcs[9][7]=8;//从高新超市到大学园
		pDoc->arcs[9][8]=10;//从高新超市到清华深圳研究生院

		pDoc->arcs[10][6]=24;//从兰羽公司到金长城公司
		pDoc->arcs[10][9]=11;//从兰羽公司到高新超市

		pDoc->arcs[11][4]=33;//从华润超市到华为通讯
		pDoc->arcs[11][6]=24;//从华润超市到金长城公司
		pDoc->arcs[11][7]=31;//从华润超市到大学园
		pDoc->arcs[11][10]=12;//从华润超市到兰羽公司


	}
	else
	{
		pDoc->arcs[0][1]=5;//从沃尔玛到华侨城
		pDoc->arcs[0][2]=12;//从沃尔玛到世界之窗
		pDoc->arcs[0][3]=16;//从沃尔玛到南江百华

		pDoc->arcs[1][4]=42;//从华侨城到华为通讯

		pDoc->arcs[2][3]=10;//从世界之窗到南江百华

		pDoc->arcs[3][4]=20;//从南江百华到华为通讯
		pDoc->arcs[3][5]=30;//从南江百华到中兴通讯
		pDoc->arcs[3][6]=27;//从南江百华到金长城公司

		pDoc->arcs[4][5]=41;//从华为通讯到中兴通讯
		pDoc->arcs[4][6]=29;//从华为通讯到金长城公司
		pDoc->arcs[4][11]=33;//从华为通讯到华润超市

		pDoc->arcs[5][6]=33;//从中兴通讯到金长城公司
		pDoc->arcs[5][7]=16;//从中兴通讯到大学园
		pDoc->arcs[5][8]=26;//从中兴通讯到清华深圳研究生院

		pDoc->arcs[6][7]=9;//从金长城公司到大学园
		pDoc->arcs[6][10]=24;//从金长城公司到兰羽公司
		pDoc->arcs[6][11]=24;//从金长城公司到华润超市

		pDoc->arcs[7][8]=13;//从大学园到清华深圳研究生院
		pDoc->arcs[7][9]=8;//从大学园到高新超市
		pDoc->arcs[7][11]=31;//从大学园到华润超市

		pDoc->arcs[8][9]=10;//从清华深圳研究生院到高新超市

		pDoc->arcs[9][10]=11;//从高新超市到兰羽公司

		pDoc->arcs[10][11]=12;//从兰羽公司到华润超市
	}
	
	//最短路径算法
	//begin
	int j,min,u;
	n=pDoc->vexnum;
	
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
			cost[i][j]=pDoc->arcs[i][j];
		cost[i][i]=0;
	}
	for(i=0;i<n;i++)
	{
		dist[i]=cost[i_begin][i];
		if(dist[i]<MAX && dist[i]>0)		//dist数组初始化
			path[i]=i_begin;			//path数组初始化(全为0)
	}
	for(i=0;i<n;i++)
		s[i]=0;
	s[i_begin]=1;
	for(i=0;i<n;i++)
	{
		min=MAX;
		u=i_begin;
		for(j=0;j<n;j++)
			if(s[j]==0 && dist[j]<min)
			{
				min=dist[j];
				u=j;
			}
		s[u]=1;
		for(j=0;j<n;j++)
			if(s[j]==0&&(dist[u]+cost[u][j])<dist[j])
			{
				dist[j]=dist[u]+cost[u][j];
				path[j]=u;		//path记录了
			}
	}
	//end
	//画出最短路径 从起点到终点
	CPen penNew(PS_SOLID,3,RGB(0,110,200));
	CPen *penOld=pDC->SelectObject(&penNew);
	CString str[12];
	int xl;
	if(s[i_end]==1)
	{		
		
		xl=0;
		u=i_end;
		while(u!=i_begin)
		{
			pDC->MoveTo(pDoc->c_Address[u]);
			str[xl]=pDoc->c_Name [u];
			u=path[u];
			pDC->LineTo(pDoc->c_Address[u]);
			xl++;
		}	
	}
	p_text2->AddString (pDoc->c_Name [i_begin]+">-");
	for(int yl=0;yl<xl;yl++)
	{
		p_text2->AddString (str[yl]+">-");
	}
	
}