找最短路系统dlg.cpp

寻找最短路系统vc实现

// 找最短路系统Dlg.cpp : implementation file
//

#include "stdafx.h"
#include "找最短路系统.h"
#include "找最短路系统Dlg.h"
#include "SetMap.h"


#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
#define maxdist 1000000
/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// Dialog Data
	//{{AFX_DATA(CAboutDlg)
	enum { IDD = IDD_ABOUTBOX };
	//}}AFX_DATA

	// ClassWizard generated virtual function overrides
	//{{AFX_VIRTUAL(CAboutDlg)
	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
	//}}AFX_VIRTUAL

// Implementation
protected:
	//{{AFX_MSG(CAboutDlg)
	//}}AFX_MSG
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
	//{{AFX_DATA_INIT(CAboutDlg)
	//}}AFX_DATA_INIT
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAboutDlg)
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
	//{{AFX_MSG_MAP(CAboutDlg)
		// No message handlers
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CMyDlg dialog

CMyDlg::CMyDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CMyDlg::IDD, pParent)
{
	for(int i=0;i<100;i++){
		for(int j=0;j<100;j++){
			distances[i][j]=maxdist;
		}
	}
	bset_begin=bset_end=false;
	for(i=0;i<100;i++){
		s[i]=false;
		dist[i]=maxdist;
		prev[i]=0;
	}
	line_nums=0;
	point_nums=0;
	fromp=0;
	top=-1;
	bset_begin=bset_end=false;
	xor=true;
	//{{AFX_DATA_INIT(CMyDlg)
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CMyDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CMyDlg)
	DDX_Control(pDX, IDC_RESULT, m_result);
	DDX_Control(pDX, IDC_SET_END, m_set_end);
	DDX_Control(pDX, IDC_MAP, m_map);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CMyDlg, CDialog)
	//{{AFX_MSG_MAP(CMyDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDC_INPUT_MAP, OnInputMap)
	ON_BN_CLICKED(IDC_SET_BEGIN, OnSetBegin)
	ON_WM_MOUSEMOVE()
	ON_WM_LBUTTONDOWN()
	ON_BN_CLICKED(IDC_SET_END, OnSetEnd)
	ON_BN_CLICKED(IDC_EXIT, OnExit)
	ON_BN_CLICKED(IDC_RESET, OnReset)
	ON_BN_CLICKED(IDC_OPEN_MAP, OnOpenMap)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CMyDlg message handlers

BOOL CMyDlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// Add "About..." menu item to system menu.

	// IDM_ABOUTBOX must be in the system command range.
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon
	
	// TODO: Add extra initialization here

	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CMyDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.

void CMyDlg::OnPaint() 
{
	
	if (IsIconic())
	{
		// device context for painting
		CPaintDC dc(this); 
		SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

		// Center icon in client rectangle
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// Draw the icon
		dc.DrawIcon(x, y, m_hIcon);

		

	}
	else
	{
	
		CDialog::OnPaint();
	}
		CClientDC dc(this);
		CString strdis;
		m_map.GetWindowRect(&map);			
		CBrush *mbrush=new CBrush(RGB(0,128,0)),*oldbrush;
		oldbrush=dc.SelectObject(mbrush);
		dc.Rectangle(10,10,map.right-map.left,map.bottom-map.top);		
		dc.SelectObject(oldbrush);
		delete mbrush;
		mbrush=new CBrush(RGB(255,0,0));
		oldbrush=dc.SelectObject(mbrush);
		for(int i=0;i<point_nums;i++){
			dc.Ellipse(points[i].x-3,points[i].y-3,points[i].x+3,points[i].y+3);
		}
		dc.SelectObject(oldbrush);
		delete mbrush;
		CPen *mpen=new CPen(PS_SOLID,1,RGB(0,0,255)),*oldpen;
		oldpen=dc.SelectObject(mpen);
		for(i=0;i<100;i++){
			for(int j=0;j<100;j++){
				if(distances[i][j]!=maxdist){
					dc.MoveTo(points[i].x,points[i].y);
					dc.LineTo(points[j].x,points[j].y);
					int midx=(points[i].x-points[j].x)/2+points[j].x;
					int midy=(points[i].y-points[j].y)/2+points[j].y;
					strdis.Format("%.2f",distances[i][j]);
					dc.SetBkColor(RGB(0,128,0));
					dc.SetTextColor(RGB(255,128,0));
					dc.TextOut(midx-2,midy-2,strdis);
				}
			}
		}
		dc.SelectObject(oldpen);
		delete mpen;
		UpdateData(true);
	

}

// The system calls this to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CMyDlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}

void CMyDlg::OnInputMap() 
{
	// TODO: Add your control notification handler code here
	bset_begin=bset_end=false;
	m_set_end.SetWindowText("设置终点");
	xor=false;

	CSetMap mMap;
	for(int i=0;i<100;i++){
		for(int j=0;j<100;j++){
			mMap.distances[i][j]=distances[i][j];			
		}
		mMap.points[i]=points[i];
	  }
	  mMap.map=map;
	  mMap.point_nums=point_nums;
	  mMap.line_nums=line_nums;
	if(mMap.DoModal()==IDOK){
	  for(int i=0;i<100;i++){
		for(int j=0;j<100;j++){
			distances[i][j]=mMap.distances[i][j];			
		}
		points[i]=mMap.points[i];
	  }
	  point_nums=mMap.point_nums;
	  line_nums=mMap.line_nums;	
	  bready=false;
	}
	UpdateData(false);
	OnPaint();

}


void CMyDlg::OnSetBegin() 
{
	// TODO: Add your control notification handler code here
	if(point_nums==0){
		MessageBox("地图上没有点!");
		return ;
	}
	bset_end=false;
	m_set_end.SetWindowText("设置终点");
	fromp=-1;
	bset_begin=true;
	top=-1;	
	OnPaint();
}

void CMyDlg::OnMouseMove(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default
	
	CDialog::OnMouseMove(nFlags, point);
}

int CMyDlg::GetPoint(POINT p)
{
   int i,index=0;
   double d=0,min=10000000;
   for(i=0;i<point_nums;i++){
		d=(p.x-points[i].x)*(p.x-points[i].x)+
				(p.y-points[i].y)*(p.y-points[i].y);
		if(d<min){
			index=i;
			min=d;
		}
   }
   return index;
}

void CMyDlg::OnLButtonDown(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default

	CClientDC dc(this);
	CPen *mpen,*oldpen;
	if(point.x<10||point.y<10||
		point.y>map.bottom-map.top||
		point.x>map.right-map.top)goto next;
	if(bset_begin){
		fromp=GetPoint(point);		
		mpen=new CPen(PS_SOLID,2,RGB(128,128,128));
		oldpen=dc.SelectObject(mpen);
		dc.Ellipse(points[fromp].x-5,points[fromp].y-5,
			points[fromp].x+5,points[fromp].y+5);
		dc.SelectObject(oldpen);
		delete mpen;
		bset_begin=false;
		Dijkstra(100,fromp);
		bready=true;
	}else if(bset_end){
		int i,j;
		if(!bready)Dijkstra(100,fromp);
		if(top!=-1&&xor&&prev[top]!=-1){			
			i=top;		
			dc.SetROP2(R2_NOT);
			mpen=new CPen(PS_SOLID,2,RGB(128,0,128));
			oldpen=dc.SelectObject(mpen);
			while(1){
				j=prev[i];				
				dc.MoveTo(points[i].x,points[i].y);
				dc.LineTo(points[j].x,points[j].y);			
				i=j;
				if(i==fromp)break;
			}
			dc.SelectObject(oldpen);
			delete mpen;
		}
			top=GetPoint(point);
			if(top==fromp){
				dist[top]=0;
				goto dis;
			}
			i=top;			
			dc.SetROP2(R2_NOT);
			mpen=new CPen(PS_SOLID,2,RGB(128,0,128));
			oldpen=dc.SelectObject(mpen);
			while(1){
				j=prev[i];
				if(j==-1){
					dist[top]=maxdist;
					break;
				}
				dc.MoveTo(points[i].x,points[i].y);
				dc.LineTo(points[j].x,points[j].y);
				i=j;
				if(i==fromp)break;
			}
			dc.SelectObject(oldpen);
			delete mpen;
dis:
			CString mm,add;
			mm="这两点之间的最短距离为：";
			add.Format("%.4f",dist[top]);
			mm+=add;
			m_result.SetWindowText(mm);
			xor=true;
	}
next:
	CDialog::OnLButtonDown(nFlags, point);
}

void CMyDlg::OnSetEnd() 
{
	// TODO: Add your control notification handler code here
	if(fromp==-1){
		MessageBox("请先输入起始点")	;
		return;
	}
	bset_end=!bset_end;
	if(bset_end){
		m_set_end.SetWindowText("结束察看");	
	}else{
		 m_set_end.SetWindowText("设置终点");
	}
	UpdateData(false);
}

void CMyDlg::Dijkstra(int n, int v)
{

	for(int i=0;i<n;i++){
		dist[i]=distances[v][i];
		s[i]=false;
		if(dist[i]==maxdist)prev[i]=-1;
		else prev[i]=v;
	}
	dist[v]=0;s[v]=true;
	for( i=0;i<n;i++){
		double temp=maxdist;
		int u=v;
		for(int j=0;j<n;j++){
			if(!s[j]&&dist[j]<temp){
				temp=dist[j];
				u=j;
			}
		}
		s[u]=true;
		for(j=0;j<n;j++){
			if(!s[j]){
				double newdist=dist[u]+distances[u][j];
				if(newdist<dist[j]){
					dist[j]=newdist;
					prev[j]=u;
				}
			}
		}
	}
}

void CMyDlg::OnExit() 
{
	// TODO: Add your control notification handler code here
	OnOK();
}

void CMyDlg::OnReset() 
{
	// TODO: Add your control notification handler code here
	bset_begin=bset_end=false;
	m_set_end.SetWindowText("设置终点");

	for(int i=0;i<100;i++){
		for(int j=0;j<100;j++){
			distances[i][j]=maxdist;
		}
	}
	bset_begin=bset_end=false;
	for(i=0;i<100;i++){
		s[i]=false;
		dist[i]=maxdist;
		prev[i]=0;
	}
	line_nums=0;
	point_nums=0;
	fromp=0;
	top=0;
	bset_begin=bset_end=false;
	UpdateData(false);
	m_result.SetWindowText("");
	OnPaint();
}

void CMyDlg::OnOpenMap() 
{
	// TODO: Add your control notification handler code here
	bset_begin=bset_end=false;
	m_set_end.SetWindowText("设置终点");
	xor=false;

	CFileDialog mdlg(1,"*.txt");
	mdlg.DoModal();
	int i,j,len=mdlg.GetPathName().GetLength();

	CString tempstr;
	char *filename;
	filename=new char[len+1];
	for(i=0;i<len;i++){
		filename[i]=mdlg.GetPathName().GetAt(i);
	}
	filename[len]=0;

    CFile infile;
	infile.Open(filename,0);
	if(!infile)	MessageBox("open failed");
	infile.Read(&point_nums,sizeof(int));
	infile.Read(&line_nums,sizeof(int));
	for(i=0;i<point_nums;i++){
		infile.Read(&points[i].x,sizeof(int));
		infile.Read(&points[i].y,sizeof(int));
	}
	for(i=0;i<point_nums;i++){
		for(j=0;j<point_nums;j++){
			infile.Read(&distances[i][j],sizeof(double));
		}
	}
	OnPaint();
}