dij.cpp

Dij算法 图论里面的 可以用来计算最短路径

#include"iostream"
#include"string.h"
#include"stdio.h"
#include"string.h"
using namespace std;
int juzhen[100][100];
int jilu[100][3];
int quchu[100];
int geshu;
void panduan(int *jinru,int *wei,int num)
{
	int i,p=0,q=0;
	for(i=0;i<geshu;i++)
	{
      if(jilu[i][0]==0)
	  {
		  wei[p]=i;
		  p++;
	  }
	  else
	  {
		  jinru[q]=i;
		  q++;
	  }
	}
}
int dij()
{
   int i,j,k,p1,q1,p,q;
   int dian1,dian2,min;
   int jianru[100];
   int weijinru[100];
   int qq[100];
   memset(jilu,0,sizeof(jilu));
   jilu[0][0]=jilu[0][2]=-1;
   jilu[0][1]=0;
   for(i=1;i<geshu;i++)
   {
      panduan(jianru,weijinru,i);//把进入的点和未进入的点分开
      j=i; //进入的点的个数
	  k=geshu-i;//未进入得点的个数
	  min=1000;
	  for(p1=0;p1<j;p1++)
	  {
		 p=jianru[p1];
         for(q1=0;q1<k;q1++)
		 {
			 q=weijinru[q1];
			 if(juzhen[p][q]==0)
				 continue;
			 if(juzhen[p][q]+jilu[p][1]<min)
			 {
				min=juzhen[p][q]+jilu[p][1];
				dian2=q;
				dian1=p;
			 }
		 }
	  }
	  jilu[dian2][0]=dian2;
	  jilu[dian2][2]=dian1;
	  jilu[dian2][1]=min;
   }
   return 0;
}
void dayin()
{
	int i;
	jilu[0][2]=0;
	for(i=0;i<geshu;i++)
		cout<<"  "<<char(i+'a')<<"----"<<char(jilu[i][2]+'a')<<":"<<jilu[i][1]<<endl;
}
int main()
{
	freopen("a.txt","r",stdin);
	int i,j;
	cin>>geshu;
	for(i=0;i<geshu;i++)
	{
		for(j=0;j<geshu;j++)
		{
			cin>>juzhen[i][j];
			cout<<juzhen[i][j];
		}
		cout<<endl;
	}
	dij();
	dayin();
	while(1);
	return 0;
}