testdijkstrawithgpheapsort.cpp

使用堆优化的最短路径算法,速度非常快,建议下载

// 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;
		for(int x=0;x<100;x++)
		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:%.2f\nVERSION:%s\n",nTime/100.0,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];
	int *mark=new int[n];
	int *Heap=new int[n];//建立堆数组，存放的是每个值的索引
	int *HeapLocate=new int[n];//用于查找每个元素在堆里面的位置^_^
	memset(mark,0,n*sizeof(int));
	for(int i=0;i<n;i++)
		path[i]=s;
	for(i=0;i<n;i++)
		d[i]=bignum;
	for(i=0;i<inputrect[s].NeibourCount;i++)
	{
		int number=inputrect[s].data[i].Number;
		ET power=inputrect[s].data[i].power;
		d[number]=power;
	}
	mark[s]=1;path[s]=0;d[s]=0;
	Heap[0]=0;
	HeapLocate[0]=0;
	int HeapIndex=0;
	
	for(i=0;i<n;i++)
	{
		if(mark[i]==0)
		{
			Heap[HeapIndex]=i;
			HeapLocate[i]=HeapIndex;
			int TempIndex=HeapIndex+1;
			while(TempIndex!=1)
			{
				if(d[Heap[TempIndex-1]]<d[Heap[TempIndex/2-1]])
				{
					int temp=Heap[TempIndex-1];
					Heap[TempIndex-1]=Heap[TempIndex/2-1];
					HeapLocate[Heap[TempIndex/2-1]]=TempIndex-1;
					Heap[TempIndex/2-1]=temp;
					HeapLocate[temp]=TempIndex/2-1;
				}
				else
				{
					break;
				}
				TempIndex/=2;
			}
			HeapIndex++;
		}
	}
	HeapIndex--;
	/*	以上为创建最小堆的过程。*/

	for(i=0;i<n;i++)
	{
		int w=Heap[0];
		if(w==t)
			break;	
	
		mark[w]=1;
		Heap[0]=Heap[HeapIndex];
		HeapLocate[Heap[HeapIndex]]=0;
		HeapIndex--;
		int TempIndex=1;
		while(TempIndex*2<=HeapIndex+1)
		{
			if(TempIndex*2!=HeapIndex+1)
			{
				int tempmin;
				if(d[Heap[TempIndex*2-1]]>d[Heap[TempIndex*2]])
				{
					tempmin=TempIndex*2;
				}
				else
				{
					tempmin=TempIndex*2-1;
				}
				if(d[Heap[TempIndex-1]]>d[Heap[tempmin]])
				{
					int temp=Heap[TempIndex-1];
					Heap[TempIndex-1]=Heap[tempmin];
					HeapLocate[Heap[tempmin]]=TempIndex-1;
					Heap[tempmin]=temp;
					HeapLocate[temp]=tempmin;
					TempIndex=tempmin+1;
				}
				else
				{
					break;
				}
			}
			else
			{
				if(d[Heap[TempIndex-1]]>d[Heap[TempIndex*2-1]])
				{
					int temp=Heap[TempIndex-1];
					Heap[TempIndex-1]=Heap[TempIndex*2-1];
					HeapLocate[Heap[TempIndex*2-1]]=TempIndex-1;
					Heap[TempIndex*2-1]=temp;
					HeapLocate[temp]=TempIndex*2-1;
					TempIndex=TempIndex*2;
				}
				else
				{
					break;
				}
			}
		}
		
		//以上为删除堆顶元素
		for(int j=0;j<inputrect[w].NeibourCount;j++)
		{
			int number=inputrect[w].data[j].Number;
			ET temp=d[w]+inputrect[w].data[j].power;
			if(mark[number]==0&&d[number]>temp)
			{
				d[number]=temp;
				path[number]=w;
				
				TempIndex=HeapLocate[number]+1;
				while(TempIndex!=1)
				{
					if(d[Heap[TempIndex-1]]<d[Heap[TempIndex/2-1]])
					{
						int tmp=Heap[TempIndex-1];
						Heap[TempIndex-1]=Heap[TempIndex/2-1];
						HeapLocate[Heap[TempIndex/2-1]]=TempIndex-1;
						Heap[TempIndex/2-1]=tmp;
						HeapLocate[tmp]=TempIndex/2-1;
					}
					else
					{
						break;
					}
					TempIndex/=2;
				}//调整堆次序
				
			}
		}
	
	}
	ET rlt=d[t];
	delete[] d;
	delete[] mark;
	delete[]Heap;
	delete[]HeapLocate;
	return rlt;
}