dijkstra.cpp

这是帮那留学生做的第二个作业,里面有详细的文档资料,要求运用到 链表 图 和最短路径算法. Dijkstra

// Dijkstra.cpp: implementation of the Dijkstra class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Dijkstra.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

Dijkstra::Dijkstra()
{
	
}

Dijkstra::~Dijkstra()
{
	delete [] table;
	
}

int * Dijkstra::findpath(town *towns,int number,int start)
{
/*
	//test
	connection *testhand=NULL;
	for(int testi=0;testi<number;testi++)
	{
		testhand=towns[testi].connections.hand;
		cout<<towns[testi].name<<"  ";
		while(testhand!=NULL)
		{
			cout<<testhand->town<<":"<<testhand->dist<<"   ";
			testhand=testhand->next;
		}
		cout <<endl;
		
	}

*/

	//--------------------------
	int *shortpath;
	table=new Table[number];
	
	//initalize Table
	for(int i=0;i<number;i++){
		table[i].dist=Infinity;
		table[i].known=0;
		table[i].path=NotAVertex;
	}

	table[start].dist=0;
	
	//---------------------------------
	int v,w;
	connection *hand=NULL;
	int tmpdist=Infinity;
	int tmppost=NotAVertex;
	for(;;)
	{
		//------------
		for(int i=0;i<number;i++){
			if((!table[i].known)&&table[i].dist<tmpdist){
				tmppost=i;
				tmpdist=table[i].dist;
			}
		}
		if(tmppost==NotAVertex)
			break;
		//-------------
		table[tmppost].known=1;
		//-----------------
		hand=towns[tmppost].connections.hand;
		while(hand!=NULL)
		{
			if(!table[hand->town].known){
				if(table[tmppost].dist+hand->dist<table[hand->town].dist)
				{
					table[hand->town].dist=table[tmppost].dist+hand->dist;
					table[hand->town].path=tmppost;
				}
			}
			hand=hand->next;
		}
		
		//initalize
		hand=NULL;
		tmpdist=Infinity;
		tmppost=NotAVertex;		
	}
	
	shortpath=new int[number];
	for(int j=0;j<number;j++){
		shortpath[j]=table[j].dist;
	}
	return shortpath;
	
}