分支限界法求单源路径,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 ] ); }