最短路经.txt

最短路径,非常容易看懂,且好用.希望有人可以使用.

#pragma once
#define maxPoint 100
class CGraph
{
public:
 CGraph(void);
 ~CGraph(void);
 bool SetGraph( double g[maxPoint][maxPoint] , int startPoint , int size );
 bool Dijkstra();
 void Display();
 int GetStartPoint();
 double GetBestWay( int dest , int path[] , int &pathLen );
private:
 //标志当前图是否已经求解
 bool solved;
 //当前图布局
 double graph[maxPoint][maxPoint];
 //地图大小
 int size;
 //起点
 int startPoint;
 //当前图的解
 double dist[maxPoint];
 int prev[maxPoint];
};
////////////////////////////////////////////////////////////
// Graph.cpp
#include 'StdAfx.h'
#include '.\graph.h'
CGraph::CGraph(void)
{
 for( int i = 0 ; i < maxPoint ; i++ )
 {
  for( int j = 0 ; j < maxPoint ; j++ )
   graph[i][j] = -1;
 }
 startPoint = -1;
 size = -1;
 //当前图还没有求解
 solved = false;
}
CGraph::~CGraph(void)
{
}
//
//
bool CGraph::SetGraph( double g[maxPoint][maxPoint] , int startPoint , int size 
)
{
 for( int i = 0 ; i < size ; i++ )
 {
  for( int j = 0 ; j < size ; j++ )
   graph[i][j] = g[i][j];
 }
 this->startPoint = startPoint;
 this->size = size;
 solved = false;
 Dijkstra();
 return true;
}
//
//
bool CGraph::Dijkstra()
{
 bool s[maxPoint];
 for( int j = 0 ; j < size ; j++ )
 {
  dist[j] = graph[startPoint][j];
  s[j] = false;
  //dist[i]<0，表示没有路径连接 结点startPoint 与 结点j
  if( dist[j] < 0 )
   prev[j] = 0;
  else
   prev[j] = startPoint;
 }
 //从起点出发
 dist[startPoint] = 0;
 s[startPoint] = true;
 for( int i = 0 ; i < size ; i++ )
 {
  double temp;
  int u = startPoint;
  bool flag = false;
  for( int j = 0 ; j < size ; j++ )
  {
   if( !s[j] )
   {
    //如果不是第一次比较，temp u，都已经赋值，则
    if( flag )
    {
     if( dist[j] > 0 && dist[j] < temp )
     {
      u = j;
      temp = dist[j];
     }
    }
    else
    {
     u = j;
     temp = dist[j];
     flag = true;
    }
   }
  }
  s[u] = true;
  for( int j = 0 ; j < size ; j++ )
  {
   if( !s[j] && graph[u][j] > 0 )
   {
    double newDist = dist[u] + graph[u][j];
    if( dist[j] < 0 || newDist < dist[j] )
    {
     dist[j] = newDist;
     prev[j] = u;
    }
   }
  }
 }
 //标记当前问题已经解决
 solved = true;
 return true;
}
//
//
void CGraph::Display()
{
 printf( '当前地图的邻接矩阵\n' );
 for( int i = 0 ; i < size ; i++ )
 {
  for( int j = 0 ; j < size ; j++ )
  {
   printf( '%5.f' , graph[i][j] );
  }
  printf( '\n' );
 }
}
//
//
double CGraph::GetBestWay( int dest , int path[] , int &pathLen )
{
 int p = dest;
 int theway[maxPoint];
 int len = 0;
 while( p != startPoint )
 {
  theway[len] = p;
  p = prev[p];
  len++;
 }
 theway[len] = startPoint;
 len++;
 for( int i = 0 , j = len - 1 ; i < len ; i++ , j-- )
  path[i] = theway[j];
 pathLen = len;
 return dist[dest];
}
//
//
int CGraph::GetStartPoint()
{
 return startPoint;
}
//

////////////////////////////////////////////////////////////
// Dijkstra.cpp : 定义控制台应用程序的入口点。
//
#include 'stdafx.h'
#include 'conio.h'
#include 'Graph.h'
int _tmain(int argc, _TCHAR* argv[])
{
 double graph[][maxPoint] =
 {
  { 1 , 10 , -1 , 30 , 100 } ,
  { -1 , 0 , 50 , -1 , -1 } ,
  { -1 , -1 , 0 , -1 , 10 } ,
  { -1 , -1 , 20 , 0 , 60 } ,
  { -1 , -1 , -1 , -1 , -1 }
 };
 int size = 5;
 int start = 0;
 int dest = 1;
 int pathlen;
 int path[maxPoint];
 double dist;
 CGraph g;
 g.SetGraph( graph , start , size );
 g.Display();
 printf( '----------------------------------------\n' );
 for( dest = 0 ; dest < size ; dest++ )
 {
  dist = g.GetBestWay( dest , path , pathlen );
  printf( '从 %d 到 %d 的最短路径长 %.f\n' , g.GetStartPoint() , dest , dist );
  printf( '所经结点为:\n' );
  for( int i = 0 ; i < pathlen ; i++ )
   printf( '%3d' , path[i] );
  printf( '\n----------------------------------------\n' );
 }
 getch();
 return 0;
}