dijkstraview.cpp

DijkstraPrj算法的实现

// DijkstraView.cpp : implementation of the CDijkstraView class
//

#include "stdafx.h"
#include "Dijkstra.h"

#include "DijkstraDoc.h"
#include "DijkstraView.h"

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


/////////////////////////////////////////////////////////////////////////////
// CDijkstraView

IMPLEMENT_DYNCREATE(CDijkstraView, CView)

BEGIN_MESSAGE_MAP(CDijkstraView, CView)
	//{{AFX_MSG_MAP(CDijkstraView)
	ON_COMMAND(ID_DIJKSTRAL, OnDijkstral)
	//}}AFX_MSG_MAP
	// Standard printing commands
	ON_COMMAND(ID_FILE_PRINT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_DIRECT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_PREVIEW, CView::OnFilePrintPreview)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CDijkstraView construction/destruction

CDijkstraView::CDijkstraView()
{
	// TODO: add construction code here

}

CDijkstraView::~CDijkstraView()
{
}

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

	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CDijkstraView drawing

void CDijkstraView::OnDraw(CDC* pDC)
{
	CDijkstraDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	// TODO: add draw code for native data here
}

/////////////////////////////////////////////////////////////////////////////
// CDijkstraView printing

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

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

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

/////////////////////////////////////////////////////////////////////////////
// CDijkstraView diagnostics

#ifdef _DEBUG
void CDijkstraView::AssertValid() const
{
	CView::AssertValid();
}

void CDijkstraView::Dump(CDumpContext& dc) const
{
	CView::Dump(dc);
}

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

/////////////////////////////////////////////////////////////////////////////
// CDijkstraView message handlers



///////////////////////////////////////////////////////////////////////
//


void CDijkstraView::OnDijkstral() 
{
	
	int nEdges=SUM_EDGE;
	int S=1;				// 初始节点
	int T=10;				// 终结节点
	int path[SUM_NODE];		// 前置路径节点
	int pathLen;

	EDGE edges[SUM_EDGE]={	//定义所有的边，以及相关拓扑
		{1,1,5,12},		{2,5,6,5},		{3,6,7,9},		{4,7,8,7},
		{5,8,10,14},	{6,1,2,11},		{7,2,3,10},		{8,2,4,8},
		{9,5,9,30},		{10,3,8,17},	{11,5,3,19},	{12,7,9,16},
		{13,3,6,10},	{14,3,7,15},	{15,9,10,6}
	};

	

	//输出结果:1
	FILE *fp;
	fp=fopen("result.txt","w");

	char cc[36];
	CString strpath;
	CClientDC dc(this);

	for(int i=1;i<SUM_NODE;i++)
		for(int j=i+1;j<=SUM_NODE;j++){
		S=i; T=j;
		pathLen=Dijkstral(edges,nEdges,S,T,path);
	
		//找到终端T的最短路径	
		strpath="";
		::sprintf(cc,"%-5d",S);	
		strpath="起点：";strpath+=cc;
		::sprintf(cc,"%-5d",T);
		strpath+="  终点：";strpath+=cc;
		::sprintf(cc,"%-5d",pathLen);	
		strpath+="  长度：";strpath+=cc;
		dc.TextOut(100,100,strpath);
		fprintf(fp,"%s  ",strpath);

		strpath="路径：";
		for(int k=0;k<SUM_NODE;k++){
			::sprintf(cc,"%d",path[k]);
			strpath+=cc;strpath+="  ";			
			if(path[k]==T){
				dc.TextOut(100,130,strpath);
				fprintf(fp,"%s\n",strpath);
				break;
			}
			if(pathLen==0||pathLen>=MAX_VALUE){				
				fprintf(fp,"\n");
				break;
			}
		}

	}

	fclose(fp);
}

int CDijkstraView::Dijkstral(Edge *pEdges, int nEdges, int S, int T,int *pPath)
{
	int NodeFlag[SUM_NODE];		// Node[i] 0未标记 1临时标记 2永久标记
	int U[SUM_NODE];			// U[i]表示与节点Node[i]到起始点最短距离预测值
	int PreNode[SUM_NODE];		// PreNode[i]为当前取得U[i]值的前搜节点号
	int currentNode,u,minUNode;	// 当前处理的节点 最小的U[i]，即u
	int tempNode,forEver;

	int i,j;	
	
	if(S==T){
		return (0);	
	}

	for(i=0;i<SUM_NODE;i++){
		NodeFlag[i]=0;	//置全部为标记
		U[i]=MAX_VALUE;	//初始化各个节点的最小路径
		PreNode[i]=0;	//初始化各个节点的前索节点 可以不初始化
		pPath[i]=0;
	}

	//第一步：初始化起始点
	NodeFlag[S-1]=2;  
	U[S-1]=0;
	currentNode=S;    
	
	for(i=0;i<SUM_NODE;i++){
	// 第二步：遍历所有未标记节点，置临时节点
	// 从未标记节点中选择与当前点相关的节点(当前节点就是和u对应的节点)
	// 一次循环只能标记一个永久节点，所以要循环SUM_NODE次，除非找到路径break
		u=MAX_VALUE;
		for(j=0;j<SUM_EDGE;j++){
			tempNode=-1;
			if(pEdges[j].headNodeId	== currentNode)tempNode=pEdges[j].endNodId;
			if(pEdges[j].endNodId	== currentNode)tempNode=pEdges[j].headNodeId;
			// 和当前点相关的未标记点			
			if(tempNode!=-1&&NodeFlag[tempNode-1]==0){
				NodeFlag[tempNode-1]=1;	
			}		
	//第三步：临时标记节中寻找最小U值
			if(NodeFlag[pEdges[j].headNodeId-1]==1&&
				NodeFlag[pEdges[j].endNodId-1]==2){				
				tempNode=pEdges[j].headNodeId;
				forEver=pEdges[j].endNodId;
			}else if(NodeFlag[pEdges[j].headNodeId-1]==2&&
				NodeFlag[pEdges[j].endNodId-1]==1){
				tempNode=pEdges[j].endNodId;
				forEver=pEdges[j].headNodeId;
			}else{	continue;  }			
			// 为临时节点设置U值			
			if(U[tempNode-1]>U[forEver-1]+pEdges[j].wight){
				U[tempNode-1]=U[forEver-1]+pEdges[j].wight;	
				PreNode[tempNode-1]=forEver;
			}
			// 记录最小U值
			if(u>U[tempNode-1]){
				u=U[tempNode-1];	// 记录较小值
				minUNode=tempNode;	// 较小值对应的节点 循环完了之后minU就是最小值了											
			}	
		}
		//所有的节点都过了一遍，完成了临时节点标记，记录了最小的U以及对应的节点
		//
		currentNode=minUNode;

		if(u>=MAX_VALUE){// 没有最短路径
			return (MAX_VALUE);			
		}
		if(currentNode==T){ // 找到路径，整理
			j=SUM_NODE;	tempNode=T;
			do{			
				pPath[--j]=PreNode[tempNode-1];
				tempNode=PreNode[tempNode-1];
			}while(tempNode!=S&&j>=0);
			for(int k=0;j<SUM_NODE;j++,k++){
				pPath[k]=pPath[j];
			}
			pPath[k]=T;
			return (u);	
		}
	// 第四步：S=S+{currentNode}  永久标记一个点minNode
		NodeFlag[currentNode-1]=2;			
	}
	return (u);	
}