dijkstra.cpp

这是本人精心搜集的关于常用图论算法的一套源码

#include <iostream.h>
#include <iomanip.h>
//单源最短路径的Dijkstra算法
#define MAX 10 //假定有向网中最多10个顶点
#define BOUND 10000 // 程序中用10000代表∞,并将其命名为BOUND
//定义从源点到某顶点的路径的存储结构
struct pathInfo  
{  int num;    
   int nodes[MAX];
};

void shortDijkstra()
{  int cost[MAX][MAX]; //cost为带权有向图的邻接矩阵   
   int s[MAX]; //s[i]==1表示已找到从源点到终点i的最短路径   
   int dist[MAX]; //dist存储路径长度   
   pathInfo path[MAX]; //path存储从源点到各终点的最短路径   
   int count, x; //顶点个数及源顶点编号(从0开始)   
   //建立有向图,初始化相应数据   
   cout<<"输入顶点个数及源顶点编号(顶点编号从0开始)";   
   cin>>count>>x; //假定顶点个数count不会超过MAX   
   int inx1, inx2;   
   for(inx1=0; inx1<count; inx1++) s[inx1]=0; //初始状态,所有顶点都不在集合S中   
   s[x]=1;  //源点x放入S集中   
   cout<<"依次输入各弧权值(-1代表两顶点之间无弧)";   
   for(inx1=0; inx1<count; inx1++) 
     for(inx2=0; inx2<count; inx2++)       
        {  cin>>cost[inx1][inx2]; //假定输入的权值是有效的正整数
           if(cost[inx1][inx2]==-1) cost[inx1][inx2]=BOUND;      
        }   
     for(inx1=0; inx1<count; inx1++) //初始化最短距离数组dist   
        {  dist[inx1]=cost[x][inx1];       
           if(dist[inx1]<BOUND)     //初始化路径数组      
             {  path[inx1].num=1; path[inx1].nodes[1]=inx1; }
           else path[inx1].num=0;     
        }//end_for
       //选择N-1条最短路径,并依次输出最短路径   
     int minWeight,min;   
     for(inx1=1; inx1<count; inx1++)     
        {  minWeight=BOUND; min=x;      
           for(inx2=0; inx2<count; inx2++) //选取最小值         
               if(!s[inx2] && dist[inx2]<minWeight)          
                 {  minWeight=dist[inx2]; min=inx2;  }
           if(minWeight==BOUND) break; //已无路径可达其余顶点,跳出循环
            else s[min]=1;     //找到新顶点的最短路径,将其加入S集
           for(inx2=0; inx2<count; inx2++) //调整dist数组元素的值
            if(!s[inx2]&& dist[min]+cost[min][inx2]<dist[inx2])
              {  dist[inx2]=dist[min]+cost[min][inx2];             
                 path[inx2]=path[min]; path[inx2].num++;            
                 path[inx2].nodes[path[inx2].num]=inx2;         
              }//end_if      
           //输出当前情况下各顶点的最短距离与最短路径
           cout<<"选出的新顶点w="<<min<<" 选出w后,修改dist数组,得到：\n"; 
           for(inx2=0; inx2<count; inx2++) cout<<setw(6)<<dist[inx2]; //输出最短距离
           cout<<"\n";      
           for(inx2=0; inx2<count; inx2++)    //输出最短路径      
              {  int len=path[inx2].num;         
                 if(len==0) cout<<setw(6)<<" ";         
                  else         
                   {  cout<<"("<<x<<",";            
                      for(int order=1; order<len; order++)                
                          cout<<path[inx2].nodes[order]<<",";            
                      cout<<inx2<<")";         
                   }       
		}//end_for      
           cout<<endl;   
        }
}

void main()
{  shortDijkstra();   }