学步园

// thebestpath.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "stdlib.h"
#define NODENUM 6
#define    STARTNODE 0
#define TARGENODE 3

char g_aNodes[NODENUM]={'A','B','C','D','E','F'};

int g_aDist[NODENUM][NODENUM]={
    {0,7,0,0,0,6},
    {7,0,7,0,0,6},
    {0,7,0,3,3,9},
    {0,0,3,0,4,0},
    {0,0,3,4,0,8},
    {6,6,9,0,8,0}};

float g_aBroken[NODENUM][NODENUM]={
    {0,0.7,0,0,0,0},
    {0.7,0,0,0,0,0},
    { 0 ,0,0,0,0,0},
    { 0 ,0,0,0,0,0},
    {0,0,0,0,0,0.6},
    {0,0,0,0,0.6,0}};

int g_ipath[NODENUM+1];

int searchPath(const int aDistMartix[NODENUM][NODENUM],int aPathStack[NODENUM+1],const int ipathDist,const float fPassed,const int iCurrNode,int iStackPoint)
/*aDistMartix[NODENUM][NODENUM]是表示图形的矩阵, aPathStack[NODENUM+1]是存储本次搜索过的路径*/
/*ipathDist 存储路径长度 fpassed存储通过效率  iCurrNode 当前节点  iStackPoint 堆中的数据数目*/
{
    int i=0,j=0,r=0;

    for (i=0;i<iStackPoint;i++)
    {
        if (iCurrNode==aPathStack[i])
        {return 0;}
        //由于此路径已经被搜索过，舍弃
    }

    aPathStack[iStackPoint++]=iCurrNode;
    //如果路径没有被搜索过，加入堆中

    for(i=0;i<NODENUM;i++)
    {
        if (aDistMartix[iCurrNode][i]>0)
        {
            if(TARGENODE==i)
                //到目的地的路径
            {
                printf("%3d:%1.2f:",ipathDist+aDistMartix[iCurrNode][i],fPassed*(1-g_aBroken[iCurrNode][i]));

                for(j=0;j<iStackPoint;j++)
                {
                    printf("%c->",g_aNodes[aPathStack[j]]);

                }
                printf("%c/n",g_aNodes[TARGENODE]);
                r++;
           
            }

            else
            {  
           
            r+=searchPath(aDistMartix,aPathStack,ipathDist+aDistMartix[iCurrNode][i],fPassed *(1-g_aBroken[iCurrNode][i]),i,iStackPoint);
            }

       }
   
  }

    return r;
}

int _tmain(int argc, _TCHAR* argv[])
{ 
    int iPN=0;
    printf("---------------------------/n");
    iPN=searchPath(g_aDist,g_ipath,0,1,0,0);
    printf("---------------------------/n  sFound Paths:%d/n/n",iPN);
    system("PAUSE");
    return 0;
}