Dijkstra算法第二套模板程序

Dijkstra算法第二套模板程序

//Dijkstra算法第二套模板程序
//分两大步骤


//1.使用Dijkstra算法记录所有最短路径
//通俗的说，就是第一步只筛选 第一标尺 满足条件的情况，也就是最短路径。 


//程序具体实现，固定化，不需要修改

vector<int> pre[MAXV];

void Dijkstra(int s) 
{
    fill(d,d+MAXV,INF);

    d[s]=0;

    for(int i=0;i<n;i++) 
    {

        int u=-1;
        int MIN=INF;

        for(int j=0;j<n;j++)
        {

            if(vis[j]==false  && d[j]<MIN   )
            {
                u=j;
                MIN=d[j];


            }



        }



        if(u==-1)
        {
            return;

        }

        vis[u]=true;

        for(int v=0;v<n;v++)
        {
            if( vis[v]==false && G[u][v]!=INF  )
            {

                if( d[u]+G[u][v] <d[v] )
                {

                    //优化d[v] 
                    d[v]=d[u]+G[u][v];

                    //清空pre[v] 
                    pre[v].clear();

                    //令v的前驱为u 
                    pre[v].push_back(u);



                }
                else if(d[u]+G[u][v]==d[v]   )
                {
                    pre[v].push_back(u);

                }


            }


        }






    }





}





//2.遍历所有最短路径，找出一条使第二标尺最优的路径 

//程序有少许区域需要视具体题意来进行修改


int optvalue;       //第二标尺最优值

//存放结点的前驱结点
vector<int> pre[MAXV];

//最优路径、临时路径
vector<int> path,temp_path;


//v为当前访问结点 
void DFS(int v)
{
    //递归边界

    //如果到达了叶子结点st（就是路径的起点） 
    if(v==st) 
    {
        //将起点st加入临时路径temp_path的最后面 
        temp_path.push_back(v);

        //存放临时路径temp_path的第二标尺的值
        int value;

        计算路径temp_path上的value值;

        if( value 优于optvalue ) 
        {
            //更新第二标尺最优值与最优路径 
            optvalue=value;

            path=temp_path;


        }

        //将刚加入的结点删除 
        temp_path.pop_back();

        return; 


    }


    //递归式

    //将当前的访问结点加入临时路径temp_path的最后面 
    temp_path.push_back(v);

    for(int i=0;i<pre[v].size();i++)
    {

        //结点v的前驱结点pre[v][i],递归 
        DFS(pre[v][i] );

    }

    //遍历完所有前驱结点，将当前结点v删除 
    temp_path.pop_back();







} 





//注意，存放在temp_path中的路径结点是逆序的，因此访问结点需要倒着进行。


//边权之和

int value=0;

//倒着访问结点，循环条件为i>0 

for(int i=temp_path.size()-1;i>0;i--) 
{
    //当前结点id,下一个结点id_next

    int id=temp_path[i];
    int id_next=temp_path[i-1];

    //value增加边id->id_next的边权 
    value+=V[id][id_next]; 




}




//点权之和

int value=0;


//倒着访问结点，循环条件为i>=0 
for(int i= temp_path.size()-1;i>=0;i--  ) 
{
    //当前结点id 
    int id=temp_path[i];

    //value增加结点id的点权

    value+=W[id];




}