?? dijkstraview.cpp
字號:
// 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);
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -