/* 
 *   Basically an O( e log n ) Dijkstra's algorithm
 */
#include "route.h"
#include "23tree.h"

extern void tinsert( TNODEPTR *root , int value , int property );
extern void tpop( TNODEPTR *root , TNODEPTR *node , int *value ,
		 int *property);
extern void tdelete( TNODEPTR *root , int value , int property );

void shortpath( int numpnodes )
{

TNODEPTR root , dumnode ;
NNODEPTR nptr ;
GNODEPTR gptr ;
int i , j , pnode , node , D , nextnode , distance ;

for( i = 1 ; i <= numpnodes ; i++ ) {
    pnode = numnodes + i ;
    nptr = pnodeArray[i].nodeList ;

    root = (TNODEPTR) NULL ;
    for( j = 1 ; j <= numnodes + numpnodes ; j++ ) {
	if( j == pnode ) {
	    tinsert( &root , 0 , j ) ;
	    nptr[j].distance = 0 ;
	    nptr[pnode].from = 0 ;
	    continue ;
	}
	nptr[j].distance = VLARGE ;
    }

    for( ; ; ) {
	tpop( &root , &dumnode , &D , &nextnode ) ;
	if( dumnode == (TNODEPTR) NULL ) {
	    break ;
	}
	gptr = gnodeArray[nextnode] ;
	for( ; gptr != (GNODEPTR) NULL ; gptr = gptr->next ) {
	    distance = gptr->length ;
	    node = gptr->node ;
	    if( nptr[node].distance > D + distance ) {
		tdelete( &root , nptr[node].distance , node ) ;
		tinsert( &root , D + distance , node ) ;
		nptr[node].distance = D + distance ;
		nptr[node].from = nextnode ;
	    }
	}

    }
}

return ;
}