graph.cpp

应用斐波纳契堆和邻接表改进单源最短路径算法

/////////////////////////////////////////////////////////////////////////////////////
#include"Graph.h"
////////////////////////////////////////////////////////////////////////////////////////

const int LARGEINT=99999;
void Graph::Insert(const int u,const int v,const int dist)
{
	HeadNodes[u].Insert(v,dist);
}
/////////////////////////////////////////////////////////////////////////////////////////
void Graph::ShortestPath(const int n,const int v)
{
	FibHeap<int> Fib; 
	Element<int> e;

	for(int i=0;i<n;i++)
	{
		s[i]=FALSE;
		dist[i]=LARGEINT;
		path[i]=-1;
	}
	for(ListNode<Node> *p=HeadNodes[v].first;p;p=p->link)
	{
		path[p->Data.Id]=v;
		dist[p->Data.Id]=p->Data.Length;
	}

    for(i=0;i<n;i++)
	{
		if(i!=v)
		{
			e.id=i;
			e.key=dist[i];
			Fib.Insert(e);
		}
	}

	s[v]=TRUE;

	dist[v]=0;
	for(i=0;i<n-2;i++)
	{
		Element<int> *ps=Fib.DeleteMin(e);
		int u=ps->id;
		s[u]=TRUE;
		for(p=HeadNodes[u].first;p;p=p->link)
		{
			if(!s[p->Data.Id])
				if(dist[u]+p->Data.Length<dist[p->Data.Id])
				{
					int k=dist[p->Data.Id]-dist[u]-p->Data.Length;
					Fib.Minus(Fib.ps1[p->Data.Id],k);
					path[p->Data.Id]=u;
					dist[p->Data.Id]=dist[u]+p->Data.Length;
				}
		}
	}
}