shortpath.cpp

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

#include "ShortPath.h"
#include <memory.h>
#include <string>
using std::string;


void CShortPath::ProcessShortPath( int start  )
{
	bool* s = new bool[n];
	int *dist = new int[n];	

	memset( dist, 0, n*sizeof( int ) );
	memset( s, false, n*sizeof( bool ) );

	for( int i = 0; i< n; ++i )
	{
		int a =  cost[start*n+i];
		dist[i] = cost[start*n+i];
		if( dist[i] != MAX_NUM )
			pathvector[i].push_back(i);
	}

	int select = 0;

	for( int i = 0; i < n; i++ )
	{
		if( start == i )
			continue;

		select = FindDirectMinPath(start, s ,dist );

		for( int j = 0; j < n; j++ )
		{
			int a1 = dist[j];
		}

		s[select] = true;

		for( int j = 0; j < n; ++j )
		{

			if( j == start )
				dist[j] = 0;

			else if( !s[j] )
			{

				int a = dist[j];
				int b = dist[select];
				int c = cost[select*n+j];
				
				if( dist[j] > dist[select] + cost[select*n+j] )
				{
					pathvector[j] = pathvector[select];
					pathvector[j].push_back( j ); 
				}

				dist[j] = GetMin( dist[j], dist[select] + cost[select*n+j] ); 
				

			}
		}

	}

	for( int k = 0; k < n; k++ )
	{
		int a = dist[k];
		cost[start*n+k] = a;
	}

}