Dijkstra算法(最短路)

Dijkstra算法(最短路)

//****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;

}

1

Dijkstra算法(最短路)

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

//Description :输出路径信息

//Return type :void

//Argument :int Path[SIZE],路径信息

//Argument :int nDest,终点

void OutputPath(int Path[SIZE],int nDest)

{

if(Path[nDest]==-1)

cout<<”没有从起点到v”<<nDest<<”的路径”<<endl;

else if(Path[nDest]==nDest) //是起点

cout<<’v’<<nDest;

else

{

OutputPath(Path,Path[nDest]); //输出前面的路径

cout<<”——>v”<<nDest; //输出这一段边

}

}

int main() //主函数

{

int Edge[SIZE][SIZE];

int i,j; //图信息

//构造图信息

2

Dijkstra算法(最短路)

for(i=0;i<SIZE;i++)

{

for(j=0;j<SIZE;j++)

Edge[i][j]=INT_MAX;

Edge[i][j]=0;

}

Edge[0][1]=10; Edge[0][2]=12;

Edge[1][3]=10;

Edge[2][4]=7;

Edge[3][0]=15; Edge[3][1]=12; Edge[3][4]=7;

int Path[SIZE]; //记录最短路径信息

int nPathLength=Dijkstra(Edge,0,4,Path) //计算v0到v4的最短路径长度

if(nPathLength==INT_MAX)

cout<<”从v0到v4没有路径可通”<<endl;

else

{

cout<<” 从v0到v4的路径为：”<<endl;

OutputPath(Path,4); //输出v0到v4的最大路径

cout<<endl;

cout<<” 路径长度为：”<<nPathLength<<endl; //输出路径长度

}

return 0;

}

3