最短路径算法

一、             程序清单：

#include"iostream.h"

#include"stdlib.h"

#define MAXPOINT  4//定义最大的顶点数目

 

#define limit  99999   //设置没有路径的权代替无穷大

 

struct record{          //没个顶点的数据结构设置为一个数组队列

int number;  //顶点号

int flag;    //标志是否从队列中被选过如果为1表示选过为0表示未选

int allpath;  //从源点到这个点的当前最短距离（权最小）

}path[MAXPOINT+1];  

 

int cost[MAXPOINT+1][MAXPOINT+1];  //用来表示图的邻接矩阵

 

void main()

{int  i,j,temp,front=1,rear=MAXPOINT,N,minnumber;

//temp表示在数组队列中的当前下标 front表示队列首 rear表示队列尾

//N 表示待输入的源点号码 minnumber 表示选中的点的号码

int  min=99999;           //设置一个初始值

for(i=1;i<=MAXPOINT;i++)

for(j=1;j<=MAXPOINT;j++)

{cout<<"请输入从第"<<i<<"点到第"<<j<<"点的路径长度(权)如果没有路径的话请输入'99999'  "<<endl;

  cin>>cost[i][j];        //初始化所有点之间的（权）路径值

}

 

 

//cout<<"请输入源点号"<<endl; //输入一个起点

//cin>>N;

 

for(N=MAXPOINT;N>=1;N--)//把每一个点轮流地都设置为起点，可以求出任意一对顶点之间的最短路径

 

{ for(i=front;i<=rear;i++) //初始化每个点的信息

{if(i==N)

     path[i].allpath=0;

  else

   path[i].allpath=limit;

  path[i].flag=0;           

  path[i].number=i;

}

 

  while(rear>=1)    //控制循环次数

  {for(temp=front;temp<=MAXPOINT;temp++)

  {   if(path[temp].allpath<min&&path[temp].flag==0)//选出一个具有最值

//的点

     

  {  minnumber=path[temp].number;

           min=path[temp].allpath ;

  }

       

  }

   min=99999;

 

  path[minnumber].flag=1;//把选中的点的标志变量置1表示已经被选过避免选中

 

 

   for(i=1;i<=MAXPOINT;i++)//进行类似广度优先搜索，更新最短路径

   {if((i!=minnumber)&&(path[minnumber].allpath+cost[minnumber][i]<path[i].allpath))

      path[i].allpath=path[minnumber].allpath+cost[minnumber][i];

   }

 

   rear--;//次数减1

  }

rear=MAXPOINT; //恢复数组以便于下一点的循环

for(j=1;j<=MAXPOINT;j++)

{ cout<<"第"<<N<<"点到第"<<j<<"点的最短路径长度（权）为";

cout<<path[j].allpath <<endl;

}

 

}

 

}

二、        程序截图

 

略