最长路径dp算法.cpp

最长路径DP算法 根据邻近矩阵,再运用DP算法计算出图中任意节点间的最长路径,有点类似于最短路径算法

//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include   <iostream>
#include   <vector>
#include <conio>
//---------------------------------------------------------------------------
#pragma argsused

//   解Zark最长路径问题的DP算法。
//   ALNG   2003-6-11
//
//---------------------------------------------------------------------------
//   输入文件的格式
//   源   目标
//   顶点数
//   邻接矩阵
//
//   示例输入文件input.txt,就是zark给出的示例图
//   0   2   
//   4
//   0   1   0   1
//   0   0   1   0   
//   0   0   0   0   
//   0   1   0   0
//   
//   输出   
//   路径长度
//   路径   
//   
//   示例输出   
//   3   
//   0   3   2

typedef  std::vector< std::vector<unsigned> >   matrix; //相当于二维数组
matrix   max_paths;     //存储最长路径长度的矩阵
matrix   max_path_next_vert;   //用于构造出最长路径
matrix   adj_matrix;     //邻接矩阵
    
//max_paths中用到的特殊值   
const unsigned  unknown = 0;
const unsigned  nopath = unsigned (-1); //表明两个顶点间的最长路径长度未知
    
    
//从标准输入中读入邻接矩阵
//input:
//n[in]:count of  vertices
//
//remark:   this   function   modifies   global   variable   max_paths   and   adj_matrix   
void   read_adj_matrix(unsigned  int  n)
{   
        //read   adjacent   matrix   from   stand   input
        adj_matrix.resize(n); //邻接矩阵
        std::cout<<"输入整个图的邻接矩阵："<<std::endl;
        for(unsigned int i=0; i<n; ++i)
        {
                adj_matrix[i].resize(n);   
                for(unsigned int j=0;  j<n;  ++j)
                {
                        std::cin>>adj_matrix[i][j];
                }   
        }

        //initialize   max_paths, set all of its elements to unknown   
        max_paths.resize(n);  //存储最长路径长度的矩阵
        max_path_next_vert.resize(n);  //用于构造出最长路径
             
        for(unsigned int i=0; i<n; ++i)
        {
                max_paths[i].resize(n);
                max_path_next_vert[i].resize(n);   
                for(unsigned int j=0; j<n; ++j)
                        max_paths[i][j] = unknown;
        }
}

//   取得从i到j的最大路径的长度
//
//   返回   unsigned(-1)表示没有从i到j的路径
//   其它: 关键部分

unsigned   max_path_length(unsigned   i,   unsigned   j)
{   
        if(i==j)   return   0;   //递归退出条件
    
        if(max_paths[i][j] != unknown)
                return   max_paths[i][j];   //已经计算，直接取用计算结果
    
        unsigned   max_path   =   nopath;  //最长路
        unsigned   next_vert;   //下一个节点
        for(unsigned   k=0;   k<max_paths.size();   ++k)
        {
                if(   adj_matrix[i][k]==1   )
                {         //   k是i的后继
                        unsigned   len   =   max_path_length(k,j);
                          //   这里做了局部修改，否则可能出现错误
                          //   当max_path不为nopath而len为nopath时会出现不合理的赋值动作。   
                        if(len!=nopath && (max_path==nopath || max_path<len))
                                max_path = len,   next_vert=k;
                }   
        }

        if(max_path   !=   nopath)
                ++max_path;
                     
        max_paths[i][j]=   max_path;
        max_path_next_vert[i][j]  =   next_vert;
        return   max_path;
}

    
void   longest_path(unsigned i,unsigned j)
{   
        unsigned   len;   
        if((len=max_path_length(i,j))!=nopath)
        {
                std::cout<<"最长路径长度为：";
                std::cout<<len<<std::endl;

                std::cout<<"最长路径经过的路径：";
                std::cout<<i<<"-->";
                for(unsigned   k=max_path_next_vert[i][j]; k!=j;i=k,k=max_path_next_vert[i][j])
                        std::cout<<k<<"-->";
                std::cout<<j<<std::endl;
        }
        else
                std::cout<<"there  is  no  path  between  "<<i<<"   and   "<<j<<std::endl;
            
}   


#pragma   argsused   
int   main(int   argc,   char*   argv[])   
{   
        using   std::cin;
        using   std::cout;
        using   std::endl;
        unsigned   src,   dst,   n;

        //const unsigned  path   =   unsigned(-1);
        //cout<<path;

        cout<<"依次输入源节点号  目的结点号  总共节点数：" ;
        cin>>src>>dst>>n;

        read_adj_matrix(n); //从标准输入中读入邻接矩阵
        longest_path(src,dst);  //最长路径长度，最长路径经过的路径


        getch();
        return   0;
}
//---------------------------------------------------------------------------

//---------------------------------------------------------------------------