testdijkstrawithgp.cpp

未优化的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 <windows.h>
#include <memory.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[])
{
	if(argc<3)
		return 1;
	FILE *fp=fopen("AdjMatrixLarge.txt","r");
	int	nodenum=23540;
	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=atoi(argv[1])-1;
	int t=atoi(argv[2])-1;
	
	int *path;
	DWORD nsTime=GetTickCount();
	ET rlt=Dijkstra(node,nodenum,bignum,s,t,path);
	DWORD nTime=GetTickCount()-nsTime;
	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\nElplased Time:%d\n",count,nTime);
	delete[]queue;
	return 0;
}
ET Dijkstra(GPNODE *inputrect,int n,ET bignum,int s,int t,int *&path)
{
	ET *d=new ET[n];
	int *mark=new int[n];
	path=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;
	for(i=0;i<n;i++)
	{
		ET minc=bignum;
		int w=-1;
		for(int j=0;j<n;j++)
		{
			if(mark[j]==0&&minc>=d[j])
			{
				minc=d[j];
				w=j;
				
			}
		}
		if(w!=-1)
		{
			mark[w]=1;
			/*
			memset(temprecord,0,sizeof(int)*n);
						for(j=0;j<inputrect[w].NeibourCount;j++)
						{
							temprecord[inputrect[w].data[j].Number]=1;
							tempvalue[inputrect[w].data[j].Number]=inputrect[w].data[j].power;
						}
						for(j=0;j<n;j++)
						{
							if(mark[j]==0)
							{
			
								if(temprecord[j]==1)
								{
									if(d[j]>d[w]+tempvalue[j])
									{
										d[j]=d[w]+tempvalue[j];
										path[j]=w;
									}
									
								}
							}
						}*/
			for(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;
				}
			}
			if(w==t)
				break;
		}
		else
			break;
	}
	ET rlt=d[t];
	delete[] d;
	delete[] mark;
	return rlt;
}