问题描述
给定一个带权有向图 G=(V,E) ，其中每条边的权是一个非负实数。
另外，还给定 V 中的一个项点，称为源。
现在我们要计算从源到所有其他各项点的最短路径长度。
这里的长度是指路上各边权之和。
这个问题通常称为单源最短路径问题。
算法基本思想
Dijkstra算法是解单源最短路径问题的一个贪心算法。
其基本思想是，设置一个基点集合 S ，并不断地作贪心
选择来扩充这个集合。
一个项点属于集合 S 当且仅当从源到该项点的最短路
径长度已知。
初始时，S中仅含有源。设 u 是 G 的某一个项点，
我们把从源到 u 且中间只有经过 S 中项点的路称为
从源到 u 的特殊路径，并且数组 dist 来记录当前每个
项点所对应的最短特殊路径长度。
Dijkstra算法每次从 V-S 中取出具有最短特殊路径长度
的项点 u ，将 u 添加到 S 中，同时对数组 dist 作必要
的修改。
源程序:
////////////////////////////////////////////////////////////
// 程序员：黄江斌
// 功能：用 "贪心法" 解 "单源最短路径"
// 时间：18:58 2005-10-21
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
// 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;
in
