分支限界法求单源路径，C语言版

#include <stdio.h>
#include <stdlib.h>

int size = 0 ;

typedef struct minHeapNode
{
    int v ;            //顶点编号
    int length ;    //源点距该顶点距离
} minHeapType  ;



int isFull(   )
{
    if( size==100 )
        return 1 ;
    else
        return 0 ;
}


int isEmpty(   )
{
    if( size==0 )
        return 1 ;
    else
        return 0 ;
}



void insertMinHeap( minHeapType minHeap[] , minHeapType item  )
{
    int parent ,child ;

    if( !isFull(  ) )
    {
        
    //    if( size== 0)
        size++ ;

        for( child=size;  child>1; child = parent   )
        {
            parent = child/2 ;
            if( minHeap[parent].length > item.length  )
            {   
                minHeap[ child ].length = minHeap[  parent ].length ;
                minHeap[ child ].v = minHeap[ parent ].v ;
            }
            else break ;
        }
        minHeap[ child ].length = item.length ;
        minHeap[ child ].v = item.v ;
    }
}


minHeapType deleteMinHeap( minHeapType minHeap[]  )
{
    minHeapType heapHead ;
    int parent , child ;
    minHeapType item ;

    if( !isEmpty() )
    {
        heapHead = minHeap[ 1 ]  ;
        item  =  minHeap[ size ] ;
        size--;
        for( parent=1;  parent*2<=size;  parent = child  )
        {
            child = parent*2 ;
            if( child!=size && minHeap[ child ].length > minHeap[ child+1 ].length )
                child++ ;//child指向较小的孩子结点
            if( item.length > minHeap[ child ].length  )
            {
                minHeap[ parent ].length    = minHeap[ child ].length ;
                minHeap[ parent ].v = minHeap[ child ].v ;
            }
            else break ;//比较小的孩子节点还小，成为它们的父节点
        }
        minHeap[ parent ].length = item.length ;
        minHeap[ parent ].v = item.v ;
    }

    return heapHead ;
}


void creatGraph(  int graph[][20]  , int graphSize)
{
   
    int i , j ;
    int v1,v2 ;
    int endges ;//边数

    for(i=0; i<graphSize; i++ )
        for(j=0; j<graphSize; j++  )
            graph[i][j] = 999 ;

    printf("请输入边数\n") ;
    scanf("%d",&endges);
    for(i=0; i<endges; i++ )
    {
        scanf("%d%d",&v1,&v2);
        scanf("%d" , &graph[v1][v2] ) ;
    }
}



void main(    )
{
    int i ;
    int graphSize ;
    int graph[20][20] ;
    int  dis[ 20 ] , pre[ 100 ] ;    //源点距离j的距离  前驱顶点，保存路径
    minHeapType minHeap[ 101 ] ;
    minHeapType E,N ;
    int path[100] , pathSize;
    int v ;


    printf( "请输入顶点数\n" ) ;
    scanf("%d", &graphSize ) ;
     creatGraph(  graph , graphSize ) ;
   

/*    printf("输入最大堆大小:") ;
    scanf("%d" , &size) ;
    printf("\n") ;
*/

    E.length = 0 ;
    E.v = 0 ;
    dis[ 0 ] = 0 ;
   
    for(i=1; i<graphSize; i++ )
        dis[i] = 999 ;

    for(i=0; i<graphSize; i++ )
        pre[i] = 0 ;

   
    do
    {
        for( i=1; i<graphSize;  i++  )//与E.v相邻的点，若满足条件则入堆
        {
            if( graph[E.v][i]<999  &&  (E.length+graph[E.v][i]<dis[ i ])  )
            {
                dis[ i ] =  E.length+graph[E.v][i] ;
                pre[ i ] =  E.v ;
            
            
                N.length = dis[ i ] ;
                N.v = i ;

                insertMinHeap( minHeap ,  N  ) ;
            }
        }
        E = deleteMinHeap( minHeap ) ;
        printf("%d\n",size);
    }while( !isEmpty() ) ;


    v=graphSize-1;//终点
    path[0] = v ;

    i=1 ;
    do
    {
        path[ i ] = pre[ v ] ;
        v = pre[ v ] ;
        i++ ;
    }
    while( pre[v]!=0 ) ;
    pathSize = i ;

    for( i=pathSize-1 ; i>=0 ; i--  )
        printf( "%d ",path[i] )  ;
    printf("\n");


    printf( "%d\n",dis[ graphSize-1 ] );

}