cdijkstra.h

一个基于启发式算法的搬运工求解程序

/*
	1:CDijikstra::Run(double *graph, int n, int source, double *dis, int *path, int *pathn, double bignum);	
		a)适用于一般图
		b)参数
			graph	:二维邻接矩阵
			n		:n * n的矩阵
			source	:原点
			dis		:保存最小距离结果的一维数组
			path	:保存路径结果的二维矩阵
			bignum	:标记邻接矩阵中不可达的边的大整数

	2:CDijikstra::Run(CTriple *adj_edge, int adj_n, int source, int n, double *dis);
		a)适用稀疏图
		b)参数
			adj_edge	:保存(v1, v2, length)的一维数组
			adj_n		:一维数组的长度
			source		:原点
			dis			:保存最小距离结果的一维数组
		c)算法
			利用优先队列实现．没有保存最小路径

	3:example

	int main()
	{
		CTriple s[10] = {CTriple(0, 1, 1), CTriple(1, 3, 1), CTriple(0, 3, 3), CTriple(2, 3, 4), CTriple(0, 2, 5)};
		double dis[5];
		int i;

		for(i = 5; i < 10; i++)
		{
			s[i] = s[i - 5];
			swap(s[i].a, s[i].b);
		}

		CDijikstra::Run(s, 10, 0, 5, dis);
		for(i = 0; i < 4; i++)
			cout << dis[i] << endl;
		return 0;
	}

	4:特别声明
		上述两个函数中的参数都必须传二维数组的首地址，即连续的一维数组。
		不能传二维指针。
*/	

#pragma once
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

class CPair
{
public:
	CPair(int _a = -1, double _b = -1): a(_a), b(_b) {}	
public:
	int a;
	double b;
};

class CTriple
{
public:
	CTriple(int _a = -1, int _b = -1, double _c = -1): a(_a), b(_b), c(_c) {}	
public:
	int a;
	int b;
	double c;
};

bool operator < (const CPair &m, const CPair &n);
bool operator < (const CTriple &m, const CTriple &n);

class CDijikstra
{
public:
	static void Run(double *graph, int n, int source, double *dis, int *path, int *pathn, double bignum);
	static void Run(CTriple *adj_edge, int adj_n, int source, int n, double *dis);
private:
	static int FindFirst(CTriple *s, int n, int first);
};

bool operator < (const CPair &m, const CPair &n)
{
	return m.a >= n.b;
}

bool operator < (const CTriple &m, const CTriple &n)
{
	if(m.a != n.a)
		return m.a < n.a;
	if(m.b != n.b)
		return m.b < n.b;
	return m.c < n.c;
}

int CDijikstra::FindFirst(CTriple *s, int n, int first)
{
	int f = 0;
	int t = n - 1;
	int m;

	while(f < t)
	{
		m = (f + t) / 2;
		if(s[m].a == first)
			break;
		if(s[m].a > first)
			t = m - 1;
		else
			f = m + 1;
	}
	while(m - 1 >= 0 && s[m - 1].a == first)
		m--;

	return m;
}

void CDijikstra::Run(double *graph, int n, int source, double *dis, int *path, int *pathn, double bignum)
{
	int *pre = new int[n];
	bool *s = new bool[n];
	int i;
	int j;
	int u;
	double temp;
	

	for(i = 0; i < n; i++)
	{
		dis[i] = *(graph + source * n + i);
		s[i] = false;
		pre[i] = dis[i] == bignum ? -2 : source;
	}
	//pre[i] == -2表示此点没有直接与源点相连
	//pre[i] == -1表示0的前驱点

	dis[source] = 0;
	s[source] = true;
	pre[source] = -1;

	for(i = 1; i < n; i++)
	{
		temp = bignum;
		u = source;
		for(j = 0; j < n; j++)
			if(!s[j] && dis[j] < temp)
			{
				u = j;
				temp = dis[j];
			}
		s[u] = true;
		for(j = 0; j < n; j++)
			if(!s[j] && *(graph + u * n + j) < bignum)
			{
				if(dis[u] + *(graph + u * n + j) < dis[j])
				{
					dis[j] = dis[u] + *(graph + u * n + j);
					pre[j] = u;
				}
			}
	}

	for(i = 0; i < n; i++)
	{
		pathn[i] = 0;
		if(pre[i] != -2)				//是否和源点相通
		{
			u = i;
			while(u != -1)
			{
				*(path + i * n + pathn[i]++) = u;
				u = pre[u];
			}
			reverse(path + i * n, path + i * n + pathn[i]);
		}
	}

	delete []pre;
	delete []s;
}

void CDijikstra::Run(CTriple *adj_edge, int adj_n, int source, int n, double *dis)
{
	priority_queue<CPair > queue;
	CPair top;
	int i;
	int p;

	sort(adj_edge, adj_edge + adj_n);
	for(i = 0; i < n; i++)
		dis[i] = -1;

	queue.push(CPair(source, 0.0));
	dis[source] = 0;
	while(!queue.empty())
	{
		top = queue.top();
		queue.pop();
		if(dis[top.a] != -1 && dis[top.a] < top.b)
			continue;
		for(p = FindFirst(adj_edge, adj_n, top.a); p < adj_n && adj_edge[p].a == top.a; p++)
			if(adj_edge[p].b != source && (dis[adj_edge[p].b] == -1 || top.b + adj_edge[p].c < dis[adj_edge[p].b]))
			{
				dis[adj_edge[p].b] = top.b + adj_edge[p].c;
				queue.push(CPair(adj_edge[p].b, dis[adj_edge[p].b]));
			}
	}
}