shortpath.h

基于SDL的图形化贪心算法演示,支持节点的拖放

#ifndef __SHORT_PATH_H___
#define __SHORT_PATH_H___

#include <memory.h>
const long MAX_NUM	= 0xffff;	

#include <deque>
#include <vector>
using namespace::std;


class CConsole;

class CShortPath
{
public:

	CShortPath( int t_n )
	{
		n = t_n;
		cost = new int[n*n];
		memset( cost, 0, sizeof( int )*n*n );
		pathvector.resize( n );
	}

	~CShortPath()
	{
		delete []cost;
	}

	int FindDirectMinPath( int start,  bool* s, int *dist )
	{
		int min =MAX_NUM;
		int index = 0;
		for( int i = 0; i < n; ++i )
		{
			if( !s[i] && start != i )
			{	
				int m = dist[i];
				if( m <= min ){
					min = m;
					index = i;
				}
			}
		}

		return index;
	}

	void ProcessShortPath( int start  );

	int GetMin( int a, int b )
	{
		if( a < b )
			return a;
		return b;
	}

	void SetCost( int row, int column, int num )
	{
		cost[row*n+column] = num;
	}

	int *cost;

	int n;

	typedef deque<int> PathDeque;

	vector< PathDeque > pathvector;

#ifdef _DEBUG
	CConsole* console;
#endif // _DEBUG

};


#endif