two_q.cpp

Two-Q双端队列最短路算法

// TWO_Q.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>

#include <queue>  //队列模版类，目前尚在研究，程序调过，可用


int _tmain(int argc, _TCHAR* argv[])
{
   using namespace std;
   int d[9];  //表示点i到起点的最短路径
   int S[9];  //表示i点的状态，0表示未标号，1表示暂时标号
   int p[9];  //表示i点的前项节点
   int c[9][9]={
	   
	             0,15,11,1000,1000,1000,1000,1000,1000,
	             15,0,1000,10,1000,8,1000,1000,1000,
				 11,1000,0,13,3,1000,1000,1000,1000,
				 7,1000,13,0,6,1000,1000,1000,1000,
				 1000,1000,1000,1000,0,1000,1000,11,1000,
				 1000,2,1000,1000,1000,0,10,1000,5,
				 1000,1000,1000,12,1000,10,0,2,1000,
				 1000,1000,1000,1000,1000,1000,1000,0,25,
				 1000,1000,1000,1000,1000,1000,20,1000,0
  
                }; //表示权重矩阵
   int s,t,i,j;  //s表示起点，t表示终点,i表示循环变量

   cin>>s;    //对s和t分别赋值；
 //  cin>>t;
//cout<<c[0][1];
   queue<int> Q1,Q2; //表示两个队列，这两个队列相连形成双队列结构

   //对上面的元素进行赋初值
   
   d[s]=0;
   S[s]=1;
   for (i=0;i<9;i++)
   {
	   if (i!=s)
	   {
		   d[i]=1000;   //对d赋值为无穷大
		   S[i]=0;
	   }
   }
   //对队列赋初值，Q1
   Q1.push(s);
   for (i=0;i<9;i++)
	   if (i!=s)
	   {
		   Q2.push(i);
	   }



	//下面开始最短路径的计算，双队列最短路径算法
 int k;
 for (k=0;k<9;k++)
  if (k!=s)
 { 
	 while(!Q2.empty())
	{
      if (!Q1.empty())
	  {
		 i=Q1.front();
		 
	     Q1.pop();
	  }//从队列Q1中删除一个节点
	  else 
	  {
		  i=Q2.front();
		//  cout<<i<<endl;
	      Q2.pop();
	  }

	  for (j=0;j<9;j++)
	  {
		  if(d[j]>d[i]+c[i][j])
		  {
			  
			 
			  d[j]=d[i]+c[i][j];

			  p[j]=i;
			  if (S[j]==0)
			  {
				  S[j]=1;
				  Q2.push(j);
				  //cout<<Q2.back ()<<endl;

			  }
			  else
			      Q1.push(j);
			  
		  }
	  }
	}
 
       //  for (i=1;i<=9;i++)     
   //int& i=Q1.back ();
  // const int& ii =Q1.front();

 // cout <<"the integer at the bace of queue ql is" << Q1.empty() <<"." <<endl;

  // cout <<"the integer at the front of queue ql is" << ii <<"." <<endl;
   
   int x;
   x=k;
  //cout<<"the shortest path is"<<endl;
   cout<<"("<<s<<":"<<k<<")";
   cout<<x<<"->";
   while(x!=s)
   { 

	   cout<<p[x]<<"->" ;
	   x=p[x];
   }
   cout<<endl;
 }
   cin>>k;
	return 0;
}