theshortestpathmethod.cpp

最短路径方法The shortest path method

#include "stdafx.h"
#include "stdio.h"
#include "conio.h"
#define INFINITY 32767
//入口参数：Graph是图的矩阵表示；
//row 是矩阵的行数；
//v0是起点的序号；
//final[i]记录从起点到第i个节点是否有路可达；


void ShortestPath_DIJ(int G[6][6],int P[6][6],int D[6],int row,int v0,bool final[])
{
 for(int v = 0;v<row;++v)
 {
  final[v] = false;
  D[v] = G[v0][v];
  for(int w = 0;w<row;++w)P[v][w] = false;//设空路径;
  if(D[v]<INFINITY)
  {
           P[v][v0] = true;
     P[v][v] = true;//自己是可以到达的;
  }
 }
 D[v0] = 0;final[v0] = true;//初始化,v0的顶点属于集合s;
 //final作为标志,final[v]为false说明v在v中,否则在s中;
 //开始主循环,每次求得v0到某个v顶点的最短路径,并加v到s集;
    for(int i = 0;i<row;++i)
 {
        int min = INFINITY;
  for(int w = 0;w<row;++w)
           if(!final[w])//w在v-s中;
       if(D[w]<min)
    {
     v = w;
     min = D[w];//w顶点离v0更近;
    }//查找当前行中权值最小的节点;
     final[v] = true;//将其加入s
  for(w = 0;w<row;++w)//更新当前最短路径及距离;
  {
   if(final[w] && (min+G[v][w]<D[w]))//修改D[w]和P[w],w属于v-s
   {//如果在s中已有的路径比经过v后在到达还要远,就选择通过v点;
               D[w] = min + G[v][w];
      P[i][w] = w; //P数组记录的是要到达i节点需要经过的节点;     
      P[w][w] = true;
   }
  }
 }
 for(i =0;i<row;i++)
  for(int j = 0;j<row;j++)
  {
   printf("\tv%d:%d",i,P[i][j]);
  }
}
int main(int argc, char* argv[])
{
 int G[6][6] = {
    INFINITY,INFINITY,10   ,INFINITY,30      ,100     ,
 INFINITY,INFINITY,5    ,INFINITY,INFINITY,INFINITY,
 INFINITY,INFINITY,INFINITY,50      ,INFINITY,INFINITY,
 INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,10      ,
 INFINITY,INFINITY,INFINITY,20      ,INFINITY,60      ,
 INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,INFINITY
 };
 int D[6] ={
 INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,INFINITY
 };
 int P[6][6];
 bool final[6];
    ShortestPath_DIJ(G,P,D,6,1,final);
 return 0;
}