/*                                                           Pontificia Universidade Catolica
 *  Campinas - Sao Paulo - Brasil
 *  abril/2004
 *
 * Algoritmo de Menor Caminho entre um no S ate um no T.
 *
 *    Grafico dirigido com arcos ponderados
 *     weigth[i][j] eh o peso do arco do no I para o no J, ou seja  weigth eh a matriz de pesos, se nao exister,
 * o valor agregado sera infinity (valor muito alto).
 *    Distance: vetor contendo os custos dos menores caminhos conhecidos ate o presente momento.
 *    Perm: vetor representando todos os nos cuja distancia ate S eh conhecida.
 *    Current: no mais recente incluido em perm, inicialmente current = s, sempre que novo no for 
 * incluido em distance, recalcular sua distancia.
 *    Precede: vetor para qual precede[i] cointem o no que precede o no i no menor caminho ate entao
 * encontrado.
 *
 * Ultima atualizacao: 07/04/2004, por Cesar Kallas - cesarkallas@gmx.net
 */
 
#define infinity 1000
#define maxnodes 1
#define member 1
#define nomember 0

void shortpath(int weight[][maxnodes], int s, int t, int *pd, int precede[])
{
	int perm[maxnodes], distance[maxnodes];
	int current, i, k, dc, 
	    smalldist,    /* menor dentre distance[i] */
	    newdist;    /* possivel novo valor para distance[i] */
	
	for(i=0; i < maxnodes; i++) 
	{
		perm[i] = nomember;
		distance[i] = infinity;
	}
	
	perm[s] = member;    /* s eh o primeiro member */
	distance[s] = 0;     /* distancia s->s = 0 */
	current = s;
	
	while(current != t)
	{
		smalldist = infinity;
		dc = distance[current];
		
		for(i=0; i < maxnodes; i++)
			if(perm[i] == nomember)
			{
				newdist = dc + weight[current][i];
				if(newdist < distance[i])
				{
					distance[i] = newdist;
					precede[i] = current;
				}
				if(distance[i] < smalldist)
				{
					smalldist = distance[i];
					k = i;
				}
			}
			current = k;
			perm[current] = member;
	}
	
	*pd = distance[i];
}