分支限界法解单源最短路径问题

问题描述

给定一个带权有向图 G=(V,E) ，其中每条边的权是一个整数。另外，还给定 V 中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。

/* 
优先队列的操作MinH返回优先队列H中就有最小优先级的元素 
    InsertxH将x插入优先队列中 
    DeleteMinH删除并返回H中具有最小优先级的元素 
*/ 
# include <stdio.h> 
# include <stdlib.h> 
# define HeapSize 1000 
# define Max 9999 
typedef struct{ 
     int i; 
     int node; 
     int length; 
}Node; 
typedef struct { 
     int n; 
     int arcnum; 
     Node * nod; 
     int * prev; 
     int ** c; 
     int * dist; 
}Graph; 
typedef struct minheap { 
     int last; 
     int maxsize; 
     Node * heep; 
}Minheap, * Heap; 
void MinHeapInit (Heap &H) { 
     H = (Heap) malloc (sizeof(Minheap)); 
     H->maxsize = HeapSize; 
     H->last = 0; 
     H->heep = (Node *) malloc ((H->maxsize + 1) * sizeof(Node)); 
} 
void HeapInsert (Node x, Heap H) { 
     int i; 
     if (H->last == H->maxsize){ 
         printf("堆已满\n"); 
         exit(0); 
     } 
     i = ++ H->last; 
     while (i != 1 && x.node < H->heep[i/2].node){ 
         H->heep[i] = H->heep[i/2]; 
         i /= 2; 
     } 
     H->heep[i] = x; 
} 
void DeleteMin (Heap H, Node * x) { 
    int i, ci; 
    Node y; 
    if (H->last == 0){
        printf("空堆\n"); 
        exit(0); 
    } 
    *x = H->heep[1]; 
    y = H->heep[H->last --]; 
    i = 1; 
    ci = 2; 
    while (ci <= H->last){ 
        if (ci < H->last && (H->heep[ci + 1].node < H->heep[ci].node)) 
            ci ++; 
        if (H->heep[ci].node > y.node) 
            break; 
        H->heep[i] = H->heep[ci]; 
        i = ci; 
        ci *= 2; 
    } 
    H->heep[i] = y; 
} 
void InitGraph(Graph &G) { 
    int i, j, k ,x; 
    printf("请输入图中的弧的个数"); 
    scanf("%d",&G.arcnum); 
    k = G.arcnum; 
    for (i = 0; i < G.n; i++) { 
        G.nod[i].i = i; 
        printf("请输入第%d个节点的内容", i); 
        scanf("%d",&G.nod[i].node); 
        G.nod[i].length = 0; 
    } 
    for (i = 0; i < G.n; i++){ 
        G.dist[i] = Max; 
        G.prev[i] = -1; 
        for (j = 0; j < G.n; j++) 
            G.c[i][j] = Max; 
    } 
    while (k){
        printf("请输入第%d条边的开始节点、结束节点下标以及边的权值\n", k); 
        scanf("%d %d %d",&i, &j, &x); 
        G.c[i][j] = x; 
        k --; 
    } 
} 
void ShortestPaths(Graph &G, int v){ 
    Heap H; 
    Node E = G.nod[v]; 
    Node N; 
    G.dist[v] = 0; 
    MinHeapInit(H); 
    HeapInsert(E,H); 
    while (1){ 
        for (int j = 0; j < G.n; j++){ 
            if ((G.c[E.i][j] < Max) && (G.c[E.i][j] + E.length < G.dist[j])){ 
                G.dist[j] = E.length + G.c[E.i][j]; 
                G.prev[j] = E.i; 
                N.i = j; 
                N.length = G.dist[j]; 
                HeapInsert(N,H); 
            } 
        } 
        if (H->last != 0) 
            DeleteMin (H, &E); 
        else 
        break; 
    } 
} 
void GreateGraph(Graph &graph){ 
    int i; 
    printf("请输入顶点数"); scanf("%d",&graph.n); 
    graph.nod = (Node *) malloc (graph.n * sizeof(Node)); 
    if (graph.nod == NULL){ 
        printf("内存分配失败\n"); 
    exit(-1); 
} 
    graph.prev = (int *) malloc (graph.n * sizeof(int)); 
    if (graph.prev == NULL){ 
        printf("内存分配失败\n"); 
        exit(-1); 
    } 
    graph.dist = (int *) malloc (graph.n * sizeof(int)); 
    if (graph.dist == NULL){ 
        printf("内存分配失败\n"); 
        exit(-1); 
    } 
    graph.c = (int **) malloc (graph.n * sizeof(int)); 
    for (i = 0; i < graph.n; i++) 
    graph.c[i] = (int *) malloc (graph.n * sizeof(int)); 
} 
void DestroyGraph(Graph graph){ 
    int i; 
    for (i = 0; i< graph.n; i++) 
        free(graph.c[i]); 
    free(graph.c); 
    graph.c = NULL; 
    free(graph.nod); 
    graph.nod = NULL; 
    free(graph.dist); 
    graph.dist = NULL; 
    free(graph.prev); 
    graph.prev = NULL; 

} 
void ShowDist(Graph G, int u){ 
    int i, k; 
    for (i = 0; i < G.n; i++) { 
        printf("\n源点u=%d到顶点%d的最短路程为%d  ", u, i, G.dist[i]); 
        printf("\n其路径为"); 
        k = i; 
        while (G.prev[k] != -1){ 
            printf(" %d ", G.prev[k]); 
            k = G.prev[k]; 
        } 
    } 
    printf("\n\n"); 
    for (i = 0; i < G.n; i++) 
        printf(" %d ",G.dist[i]); 
    printf("\n\n\n"); 
    for (i = 0; i < G.n; i++) 
        printf(" %d ",G.prev[i]); 
} 
int main(void){ 
    Graph graph; 
    int u; 
    printf("请输入源点u"); 
    scanf("%d", &u); 
    GreateGraph(graph); 
    InitGraph(graph); 
    ShortestPaths(graph,u); 
    ShowDist(graph,u); 
    DestroyGraph(graph); 
// system("pause"); 
    return 0; 
}