Dijkstra算法(最短路).doc

//****Dijkstra(最短路)算法*******//
#include<iosream> //预编译命令
#include<limits> //定义了INT_MAX
using namespace std;
unst int SIZE; //图中顶点总数
//Function name :Dijkstra
//Description :计算有向图中起点到终点的最短距离
//Return type :int,最短路的长度
//Argument :int Edge[SIZE][SIZE],输入参数,图信息
//Argument :int nStart,输入参数,起点
//Argument :int Dest,输入参数,终点
//Argument :int Path[SIZE],返回参数,路径信息
int Dijkstra(int Edge[SIZE][SIZE], int nStart, int Dest, int Path[SIZE])
{
int MinDis[SIZE]; //起点到个点最短路径长度
bool InS2[SIZE]; //标志各点是否在 S2中
//初始化
int i;
for(i=0;i<SIZE;i++)
InS2[i]=true;
InS2[nStart]=false; //初始状态只有nStart在S1中,其余在S2中
for(i=0;i<SIZE;i++)
{
MinDis[i]=Edge[nStart][i]; //初始各点的最大距离
if (Edge[nStart][i]< INT_MAX)
Path[i]=nStart; //最短路径的前一点
else
Path[i]=-1; //表示前一点不存在
}
//进行计算
while(InS2[nDest]) //当nDest还在S2内则计算
{
//查找S2中最短路径长度最小值的点
int nMinLen=INT_MAX; //最短路径长度的最小值
int nPoint=-1; //拥有最小值的点
for(i=0;i<SIZE;i++) //查找
if((InS2[i]) && (MinDis[i]<nMinLen))
{
nMinLen=MinDis[i];
nPoint=i;
}
If(nMinLen==INT_MAX) //S2中的点不能从起点走到
break;

//更新S2和MinDis
InS2[nPoint]=false; //该点从S2移入S1
for(i=0;i<SIZE;i++)
if((InS2[i]) && (Edge[nPoint][i]<INT_MAX)) //对于在S2中的带您与该点有边相连
{
int nNewLen=nMinLen+Edge[nPoint][i];
if(nNewLen<MinDis[i]) //如果原路径长
{
Path[i]=nPoint; //更新路径
MinDis[i]=nNewLen; //更新路径长度
}
}
}
Return MinDis[nDest];
}
//Function name :OutputPath
//De