用 '贪心法' 解 '单源最短路径.txt

用贪心法解单源最短路径,比较不错的一个算法,大家好好看下

源程序: 

//////////////////////////////////////////////////////////// 
// 程序员：HayMaN 
// 功能：用 '贪心法' 解 '单源最短路径' 
// 时间：18:58 2006-11-24 
//////////////////////////////////////////////////////////// 


//////////////////////////////////////////////////////////// 
// Graph.h 
#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; 
} 

//////////////////////////////////////////////////////////// 
// 程序说明： 
// 本程序在 VC++.NET 2003 上调试通过 
// 首先建立 Win32控制台应用程序，工程名为 Dijkstra 
// 工程设置默认 
// 添加 一般C++类 CGraph 
// 填写以上内容