shortest.c

matlab最短路的贪心算法

/* $Revision: 1.3 $ */
// Automatically generated by MATLAB Project Wizard version 1.0

//
// This is the gateway routine for a MATLAB Math/Graphics Library-based
// C MATLAB MEX File.

#include "mex.h"
#include <malloc.h>
#define ain  0
#define c_out 0
#define NODES 1000

double map[NODES][NODES];
int lus[NODES];
struct way 
{
	double value;
	long num;
	long get;
	struct node* pt;
	struct way* to;
};

struct node
{
	long num;
	long flag;
	long from;
	double get;
	struct way* to;
	struct node* next;
};

long  findshortest(int nodess)
{
	long i,j,nowat,lsfrom;
	double most,nowst;
	struct node* head;
	struct node* nd[NODES];
	struct node* p;
	struct node* q;
	struct way*  w;
	struct way*  v;
	head = (struct node*)malloc(sizeof(struct node));
	head->next = 0;
	q = head;
	// O(N)
	for(i = 0; i < nodess; i++)
	{
		p = (struct node*)malloc(sizeof(struct node)*nodess);
		nd[i] = p;
		p->flag = 0;
		p->num = i;
		p->to = 0;
		p->get = 9999;
		p->next = 0;
		q->next = p;
		q = p;
	}
	/// O(N^2)
	for(i = 0; i < nodess; i++)
	{
		for(j = 0;j < nodess; j++)
		{
			if(map[i][j]!=-1)
			{
				v = (struct way *)malloc(sizeof(struct way));
				v->to = 0;
				v->value = map[i][j];
				v->num = j;
				if(!nd[i]->to)
					nd[i]->to = v;
				else 
				{
					w = nd[i]->to;
					while(w->to)w=w->to;
					w->to = v;
				}
				mexPrintf("%d %.1lf \n",v->num+1,v->value);
			}
		}
	}
	nd[0]->flag = 1;
	most = 0;
	nd[0]->from = 0;
	nd[0]->get = 0;
	while(nd[nodess-1]->flag == 0)
	{
		nowst = 9999;
		for(i = 0; i < nodess; i++)
		{
			if(nd[i]->flag)
			{
				v = nd[i]->to;
				while(v)
				{
					if(nd[v->num]->flag==0 && v->value+nd[i]->get < nowst)
					{
						lsfrom = i;
						nowst = v->value+nd[i]->get;
						nowat = v->num;		
						mexPrintf("num:%d from:%d to:%d flag:%d nowst:%.1lf \n",i+1,nd[i]->from+1,v->num+1,nd[i]->flag,nowst);
					}
					v = v->to;
				}
			}
		}
		nd[nowat]->flag = 1;
		nd[nowat]->from = lsfrom;
		nd[nowat]->get = nowst;
		mexPrintf("%9.1lf\n",nowst);
	}
	for(i = 0; ;i++)
	{
		lus[i] = nowat;
		if(nd[nowat]->from==0)break;
		nowat = nd[nowat]->from;
	}
	mexPrintf("%d",1);
	for(; i>=0; i--)
		mexPrintf("->%d",lus[i]+1);
	mexPrintf("\nWay At Most:%.1lf\n",nowst);
	return nowst;
}
extern void ShortEst(const int MA,const int NA,const double *A,
					 double *C)
{
	int i,j;
	for(i = 0; i < MA; i++)
	{
		for(j = 0; j < MA; j++)
			map[i][j] = A[j*MA+i];
	}
	for(i = 0; i < MA; i++)
	{
		for(j = 0; j < MA; j++)
			mexPrintf("%.1lf ",map[i][j]);
		mexPrintf("\n");
	}
	
	C[0] = findshortest(MA);
}
void mexFunction(
				 int nlhs,              // Number of left hand side (output) arguments
				 mxArray *plhs[],       // Array of left hand side arguments
				 int nrhs,              // Number of right hand side (input) arguments
				 const mxArray *prhs[]  // Array of right hand side arguments
				 )
{
	double *A,*C;
	int MA,NA,MC,NC;
	mexPrintf("%d Inputs\n",nrhs);
	if( !mxIsDouble(prhs[ain]) || mxIsComplex(prhs[ain]))
		mexPrintf("Input Must Be Noncomplex Double.\n");
	MA = mxGetM(prhs[ain]);
	NA = mxGetN(prhs[ain]);
	mexPrintf("MA:%d NA:%d\n",MA,NA);
	MC = 1;
	NC = 1;
	plhs[c_out]=mxCreateDoubleMatrix(MC,NC,mxREAL);
	A = mxGetPr(prhs[ain]);
	C = mxGetPr(plhs[c_out]);
	ShortEst(MA,NA,A,C);
	return; 
}


// a=[-1,1,3,-1,-1,-1;1,-1,-1,2,3,-1;3,-1,-1,7,-1,8;-1,2,7,-1,-1,9;-1,3,-1,-1,-1,4;-1,-1,8,9,4,-1]