spfa.cpp

自己写的SPFA,可以给初学者参考,速度比优化Dijkstra要慢

// TestDijkstraWithGP.cpp : Defines the entry point for the console application.
//
// TestDijkstra.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <limits.h>
#include <stdlib.h>
#include <memory.h>
#include <windows.h>
#define ET double //目前暂时使用INT版本

typedef struct _DATANODE
{
	ET power;
	int Number;
}DATANODE;
typedef struct _GPNODE
{
	int NeibourCount;
	int Number;
	DATANODE *data;
}GPNODE;
ET Dijkstra(GPNODE *inputrect,int n,ET bignum,int s,int d,int *&path);

int main(int argc, char* argv[])
{
	char *filename=new char[MAX_PATH];
	if(argc>1)
	{
		memcpy(filename,argv[1],strlen(argv[1])+1);
	}
	else
	{
		printf("please enter filename:");
		scanf("%s",filename);
	}
	FILE *fp=NULL;
	while(1)
	{
		fp=fopen(filename,"r");
		if(fp==NULL)
		{
			char *extfilename=new char[(int)strlen(filename)+5];
			memcpy(extfilename,filename,(int)strlen(filename));
			memcpy(extfilename+(int)strlen(filename),".txt",5);
			fp=fopen(extfilename,"r");
			delete[]extfilename;
			if(fp==NULL)
			{
			printf("%s does not exits,please enter filename again:",filename);
			scanf("%s",filename);
			}
			else
				break;
		}
		else
			break;
	}
	delete[]filename;
	int	nodenum=0;
	//DWORD filesize=GetFileSize((void*)fileno(fp),NULL);
	fseek(fp,0,SEEK_END);
	DWORD filesize=ftell(fp);
	DWORD offset=filesize-3;
	char m='\0';
	while(m!='\n')
	{
		fseek(fp,offset,SEEK_SET);
		fread(&m,1,1,fp);
		offset--;
	}
	offset++;
	fscanf(fp,"%d",&nodenum);
	nodenum++;
	fseek(fp,0,SEEK_SET);
	GPNODE *node=new GPNODE[nodenum];
	DATANODE *temp=new DATANODE[nodenum];
	int nodecount=0;
	int node1,node2;
	ET power;
	ET bignum=1;
	node1=0;
	while(!feof(fp))
	{
		int tempnode1;
		fscanf(fp,"%d",&tempnode1);
		fscanf(fp,"%d",&node2);
		fscanf(fp,"%lf\n",&power);
		bignum+=power;
		if(tempnode1==node1)
		{
			temp[nodecount].power=power;
			temp[nodecount].Number=node2;
			nodecount++;
		}
		else
		{
			node[node1].NeibourCount=nodecount;
			node[node1].Number=node1;
			node[node1].data=new DATANODE[nodecount];
			memcpy(node[node1].data,temp,sizeof(DATANODE)*nodecount);
			nodecount=1;
			node1=tempnode1;
			temp[0].power=power;
			temp[0].Number=node2;
		}
	}
	fclose(fp);
	int s,t;
	while(1)
	{
		printf("Please Enter two number,for which is from %d to %d,enter 0 for exit:\n",1,nodenum);
		scanf("%d%d",&s,&t);
		if(s==0||t==0)
			break;
		s-=1;
		t-=1;
		printf("Calculating...\n");
		int *path;
		DWORD nStartTime=GetTickCount();
		ET rlt;
		rlt=Dijkstra(node,nodenum,bignum,s,t,path);
		DWORD nTime=GetTickCount()-nStartTime;
		printf("\n%lf\n",rlt);
		int *queue=new int[nodenum];
		int count=1;
		queue[0]=t+1;
		while(s!=t)
		{
			queue[count]=path[t]+1;
			t=path[t];
			count++;
		}
		printf("path is: ");
		for(int i=0;i<count-1;i++)
		{
			printf("%d->",queue[count-1-i]);
		}
		printf("%d\n",queue[0]);
		printf("path Count:%d\n",count);
#ifdef _DEBUG
		const char *const ver="DEBUG";
#else
		const char *const ver="RELEASE";
#endif
		printf("Elplased time:%ld\nVERSION:%s\n",nTime,ver);
		delete[]queue;
		delete[]path;
	}
	return 0;
}
ET Dijkstra(GPNODE *inputrect,int n,ET bignum,int s,int t,int *&path)
{
	path=new int[n];
	if(s==t)
	{
		path[t]=s;
		return 0;
	}
	ET *d=new ET[n];
	for(int i=0;i<n;i++)
	{
		d[i]=bignum;
		path[i]=s;
	}
	d[s]=0;path[s]=0;
	bool *visitmark=new bool[n];
	memset(visitmark,0,n);
	int *cyclequeue=new int[n];
	int queuesize=0;
	int *whosturn=cyclequeue;
	cyclequeue[0]=s;
	queuesize++;
	visitmark[s]=true;
	while(queuesize!=0)
	{
		int turn=*whosturn;
		for(i=0;i<inputrect[turn].NeibourCount;i++)
		{
			ET dtemp=d[turn]+inputrect[turn].data[i].power;
			if(dtemp<d[inputrect[turn].data[i].Number])
			{
				d[inputrect[turn].data[i].Number]=dtemp;
				if(visitmark[inputrect[turn].data[i].Number]==false)
				{
					if(whosturn+queuesize<cyclequeue+n)
					{
						*(whosturn+queuesize)=inputrect[turn].data[i].Number;

					}
					else
					{
						int diff=whosturn+queuesize-cyclequeue-n;
						*(cyclequeue+diff)=inputrect[turn].data[i].Number;
					}
					queuesize++;
					visitmark[inputrect[turn].data[i].Number]=true;
				}
				path[inputrect[turn].data[i].Number]=turn;
			}
		}
		if(whosturn!=cyclequeue+n-1)
			whosturn++;
		else
			whosturn=cyclequeue;
		queuesize--;
		visitmark[turn]=false;
	}
	ET rlt=d[t];
	delete[]d;
	delete[]visitmark;
	delete[]cyclequeue;
	return rlt;
}